관할 구역 제한

그리드토피아 시는 $R$행 $C$열의 정사각형 칸("블록")으로 이루어진 격자이다. 행은 위에서 아래로 1번부터 $R$번까지, 열은 왼쪽에서 오른쪽으로 1번부터 $C$번까지 번호가 붙는다. 이 도시에는 $S$개의 경찰서가 있다. $i$번째 경찰서는 $R_i$행 $C_i$열의 블록에 있다. 한 블록에 경찰서가 둘 이상 있는 경우는 없다.

각 경찰서는 가로나 세로로 $D_i$블록 이내에 있는 블록만 순찰할 수 있다. $i$번째 경찰서는 $\max(|R' - R_i|, |C' - C_i|) \le D_i$이면 $R'$행 $C'$열의 블록을 순찰할 수 있다. 달리 말해, $i$번째 경찰서는 자신을 중심으로 한 한 변의 길이가 $2D_i + 1$인 정사각형 안의 블록만 순찰할 수 있다.

당신은 새로 부임한 경찰청장이다. 순찰할 수 있는 경찰서 중 정확히 하나에 일부 블록을 배정해야 한다. 경찰서가 있는 블록과 어떤 경찰서도 순찰할 수 없는 블록은 배정하지 않는다. 나머지 모든 블록은 반드시 배정해야 한다. $A_i$를 $i$번째 경찰서에 배정된 블록 수라고 하자. 모든 $A_i$ 값의 최댓값과 최솟값의 차이를 최소화해 업무량을 최대한 고르게 나눠야 한다. 가능한 가장 작은 차이는 얼마인가?

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스는 $R$, $C$, $S$가 주어지는 줄로 시작한다. 이어서 $S$개의 줄에 $R_i$, $C_i$, $D_i$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 위에서 구한 차이다.

• $1 \le T \le 100$.
• $2 \le S \le 15$.
• 모든 $i$에 대해 $1 \le R_i \le R$.
• 모든 $i$에 대해 $1 \le C_i \le C$.
• 모든 $i \ne j$에 대해 $R_i \ne R_j$ 또는 $C_i \ne C_j$. (같은 블록에 경찰서가 둘 놓이지 않는다.)
• 모든 $i$에 대해 $1 \le D_i < \max(R, C)$.

예제 1에서 도시는 3행 4열의 격자이며, 경찰서 하나는 왼쪽 위 블록에, 다른 하나는 오른쪽 아래 블록의 바로 왼쪽 블록에 있다. 1번 경찰서는 자신의 블록 가장자리나 모서리에 닿은 3개 블록만 순찰할 수 있다. 나머지 블록들은 가로나 세로로 1블록보다 멀리 떨어져 있다. 2번 경찰서는 경찰서가 있는 블록을 제외한 격자의 모든 블록을 순찰할 수 있다. 1번 경찰서에 순찰 가능한 3개 블록을 모두 배정하고, 나머지 7개 블록을 2번 경찰서에 배정하면 배정 블록 수의 차이가 최소가 된다.

예제 2에서 최적의 배정 방법 중 하나는 아래와 같다. 1은 1번 경찰서, 2는 2번 경찰서, !는 1번 경찰서에 배정된 블록, @는 2번 경찰서에 배정된 블록, .는 어느 경찰서에도 배정되지 않는 블록을 나타낸다. 한 경찰서에 배정된 블록이 하나의 연속된 영역을 이룰 필요는 없다.

@@@@.
!!!@.
!2!@.
1!!@.
!@!@.