房间是一个 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。