Light Up

Light Up is a puzzle played on a rectangular board divided into unit squares. Some squares are "empty" (the white squares in the figure below) and some are "barriers" (the dark squares in the figure below). A barrier square may carry an integer $i$ with $0 \le i \le 4$.

Figure 2: (a) a puzzle with 6 rows, 7 columns and 7 barriers; (b) a solution to the puzzle.

The goal of the puzzle is to "light up" every empty square by placing lamps (drawn as circles in the figure) in some of them. Each lamp illuminates its own square, plus every square in line with it, horizontally or vertically, up to a barrier square or the edge of the board.

A winning configuration satisfies all of the following conditions:

• every empty square must be lit;
• no lamp may be lit by another lamp;
• every numbered barrier square must have exactly that number of lamps in the four squares adjacent to it (above, below, left, and right);
• non-numbered barrier squares may have any number of adjacent lamps.

Write a program that determines the smallest number of lamps needed to reach a winning configuration.

The input contains several test cases. The first line of a test case contains two integers $N$, $M$, the number of rows and the number of columns of the board ($1 \le N \le 7$, $1 \le M \le 7$). The second line contains one integer $B$, the number of barrier squares ($0 \le B \le N \times M$). Each of the next $B$ lines describes one barrier with three integers $R$, $C$, $K$: the row number ($1 \le R \le N$), the column number ($1 \le C \le M$), and the barrier number ($-1 \le K \le 4$); $K = -1$ means the barrier is unnumbered. The end of the input is indicated by a line with $N = M = 0$.

For each test case, print one line containing either the smallest number of lamps needed to reach a winning configuration, if such a configuration exists, or the words No solution.