불 밝히기

불 밝히기(Light Up)는 여러 개의 작은 정사각형 칸으로 나뉜 직사각형 판 위에서 진행하는 퍼즐이다. 판의 일부 칸은 "빈 칸"(아래 그림의 흰색 칸)이고, 일부 칸은 "벽 칸"(아래 그림의 검은색 칸)이다. 벽 칸에는 정수 $i$ ($0 \le i \le 4$)가 적혀 있을 수도 있다.

그림 2: (a) 6행 7열, 벽 7개로 이루어진 퍼즐; (b) 그 퍼즐의 한 가지 해.

이 퍼즐의 목표는 일부 빈 칸에 전구(그림에서 원으로 표시)를 놓아 모든 빈 칸을 "밝히는" 것이다. 각 전구는 자신이 놓인 칸을 밝히고, 거기에서 가로 또는 세로로 일직선을 따라 벽 칸이나 판의 끝에 닿을 때까지의 모든 칸을 함께 밝힌다.

올바른(승리) 배치는 다음 조건을 모두 만족한다.

• 모든 빈 칸이 밝혀져야 한다.
• 어떤 전구도 다른 전구에 의해 밝혀져서는 안 된다.
• 숫자가 적힌 모든 벽 칸은, 그 칸과 상하좌우로 인접한 네 칸 중 정확히 그 숫자만큼의 칸에 전구가 놓여 있어야 한다.
• 숫자가 없는 벽 칸에는 인접한 전구의 개수에 제한이 없다.

올바른 배치를 이루는 데 필요한 전구의 최소 개수를 구하는 프로그램을 작성하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 판의 행 수와 열 수를 나타내는 두 정수 $N$, $M$이 주어진다 ($1 \le N \le 7$, $1 \le M \le 7$). 둘째 줄에는 벽 칸의 개수를 나타내는 정수 $B$가 주어진다 ($0 \le B \le N \times M$). 이어지는 $B$개의 줄에는 각 벽 칸을 나타내는 세 정수 $R$, $C$, $K$가 주어지며, 각각 행 번호($1 \le R \le N$), 열 번호($1 \le C \le M$), 벽의 숫자($-1 \le K \le 4$)를 뜻한다. $K = -1$은 숫자가 없는 벽임을 뜻한다. 입력의 끝은 $N = M = 0$인 줄로 표시된다.

각 테스트 케이스마다 한 줄을 출력한다. 올바른 배치가 존재하면 그 배치를 이루는 데 필요한 전구의 최소 개수를, 존재하지 않으면 No solution을 출력한다.