Pattern
In the room, parquet flooring is to be installed, and there's a plan to create a specific pattern on the floor.
The parquet tiles are made up of 1x1 squares, each of which can be either white or black. The room itself has dimensions of NxM. The room's layout specifies the color each square should be.
There are several shapes of parquet tiles available:
Each square within a single parquet tile can have a different color. There can be multiple types of tiles with the same shape but different color patterns. Tiles of different types may also have different costs. The supply of each type of tile is unlimited. Tiles can be rotated in any direction (in increments of 90 degrees). Tiles cannot be broken or placed face down.
Initially, some parts of the floor may already be covered with tiles.
Your task is to determine the minimum cost required to cover the remaining part of the room with tiles.
Input
The first line of the input contains three numbers: N, M (the dimensions of the room), and K (the number of available tile types). 1 <= N, M <= 8, 1 <= K <= 10. Following this is the description of the desired floor pattern. This description consists of N rows with M numbers each, where 0 represents white, 1 represents black, and 2 indicates that the square is already covered with a tile. The last K rows describe the available tile types in the following format:
<shape> <cost> <color>
<Shape> is a number from 1 to 4, indicating the shape of the tile (refer to the figure above).
<Cost> is a natural number not exceeding 10000, representing the cost of one tile of this type.
<Color> consists of one to three numbers 0 or 1. The number of numbers corresponds to the number of squares that make up the tile. These numbers specify the colors of the tile's squares in the order they are numbered in the figure.
Output
Output a single number — the minimum cost of laying the tiles, or –1 if it is impossible to lay the tiles correctly.