房间是一个 n \times m 的网格，一共有 k 个窗户，都在上下左右四条边上。在第 0 时刻，每个窗户对应的格子上都会出现若干只蚊子。
蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。
假设这些蚊子都足够聪明，请问最少花费多少时刻，使得所有格子上都有至少一只蚊子？
蚊子在第 0 时刻不能动。
房间是一个 n \times m 的网格，一共有 k 个窗户，都在上下左右四条边上。在第 0 时刻，每个窗户对应的格子上都会出现若干只蚊子。
蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。
假设这些蚊子都足够聪明，请问最少花费多少时刻，使得所有格子上都有至少一只蚊子？
蚊子在第 0 时刻不能动。
第一行一个正整数 test（1 \le test \le 10）表示数据组数。
对于每组数据，第一行三个整数 n, m, k（1 \le n, m \le 1000，1 \le k \le 6）表示房间的大小和窗户的个数。
接下来 k 行，每行三个整数 x, y, z（1 \le z \le nm）表示窗户的坐标以及出现在这个窗户的初始蚊子的数目。
横坐标从 1 \dots n 编号，纵坐标从 1 \dots m 编号，数据保证窗户一定在边界上。
对于每组数据，一行一个整数表示答案。如果无解，输出 -1。
2 5 5 4 1 1 10 1 5 10 5 1 10 5 5 10 3 3 1 1 1 8
4 -1
百度之星