5300：降雨量

在1000*1000格的区域里有m个降雨云团，每个降雨云团在某个特定的格子(x, y)里，降雨云团有各自的降雨强度a，对当前的格子带来a点降雨量。不仅如此，降雨云团还会影响附近的格子：与(x,y)距离为1的格子，降雨量为a-1；与(x,y)距离为2的格子，降雨量为a-2；...；一个降雨云团最多会影响到距离为a-1的格子，那些格子的降雨量为1。多个降雨云团会使用叠加的方法影响同一个格子的降雨量。问所有格子中，降雨量最大值是多少？

定义(x1, y1)到(x2, y2)的距离是|x1-x2|+|y1-y2|。

例如在1000*1000格的区域里的左上角有3个降雨云团，第一个云团坐标位置是(2, 3)，降雨强度是3；第二个云团坐标位置是(4, 3)，降雨强度是2；第三个云团坐标位置是(4, 4)，降雨强度是2。

则最终每个区域的降雨强度如下：

其中有些格子同时受多个降雨云团的降雨强度的影响。降雨量最大值是4。

这是一道多组案例的题目。一个正整数n，表示案例的数量。（n<=100）

每组案例中，先是一个正整数m，表示降雨云团的数量；（m<=100，且n*m<=1000）

然后是m行数据，每行数据由三个正整数x、y、a组成，表示一个降雨云团所在的格子坐标是(x, y)，云团降雨强度是a。（1<=x,y<=1000，a<=3000）

针对每组案例，输出一个整数，表示所有格子中降雨量的最大值。

每组案例输出完都要换行。

1

3

2 3 3

4 3 2

4 4 2

4

厦门大学嘉庚学院第十二届编程大赛