SP309 RATTERN - The Room Pattern

决定在一间大小为NxM的房间里铺一层地板。方式是在地板上画一些图案。房间的地板是由1x1的正方形组成的瓷砖，每一块都可以是白色的，也可以是黑色的。房间的地图上规定了房间每个方格的所需颜色。 有四种不同形式的瓷砖：（见上图） 一块瓷砖的方格可以用不同的颜色涂上。有些类型的瓷砖可以是相同的形状，但油漆不同。不同类型的瓷砖可以有不同的成本。每种类型的可用瓷砖数量不受限制。瓷砖被允许以某种方式旋转(以90度的倍数)，但它不允许打破一个瓷砖或把它的面板向下。最初，地板的任何部分都可以用瓷砖铺设。请您计算铺砌房间其余部分所需的最低成本。

t-测试样例的数量。 对于每组测试样例。第一行中，写了三个数字：N，M (房间的大小)和 K (可访问类型的瓷砖数目)。(1

对于每个测试样例输出一个整数：放置剩余部分的最小成本，如果不能执行任务，输出 -1。