SP309 RATTERN - The Room Pattern

It was decided to make a parquet floor in a room of size NxM. The idea is to lay out some pattern on the floor. The parquet tiles with which the floor of the room looks best consist of squares 1x1, each of which can be either white or black. The required color of each square of the room is specified on the map of the room. There are four different forms of parquet tiles:  Squares of one parquet tile can be painted differently. Some types of tiles can be of identical shape, but painted differently. Tiles of different types can have different cost. The number of available tiles of each type is not limited. Tiles are allowed to be turned around somehow (by an angle which is a multiple of 90 degrees), but it is not permitted to break a tile or to put it face sheet downwards. Initially, any part of the floor can be already laid out by tiles. You are requested to calculate the minimal cost of the tiles necessary to pave the remaining part of the room.

_t_ – the number of test cases, then _t_ test cases follow. In the first line of each test case three numbers are written: _N, M_ (the sizes of the room) and _K_ (number of accessible types of tiles). _\[1

For each test case output one integer: the minimal cost of laying the remaining part of the parquet, or -1 if the task cannot be performed.