Problem Description

房间是个 $n*m$ 的网格，一共有 $k$ 个窗户，都在上下左右四条边上。在第 0 时刻，每个窗户对应的格子上都会出现若干只蚊子。

蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。

假设这些蚊子都足够聪明，请问最少花费多少时刻，使得所有格子上都有至少一只蚊子？

蚊子在第 0 时刻不能动。

Input

第一行一个正整数 $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...n$ 编号，纵坐标从 $1...m$ 编号，数据保证窗户一定在边界上。

Output

对于每组数据，一行一个整数表示答案。如果无解，输出 -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