#2177. 躲避导弹

躲避导弹

题目描述

有一个r×cr×c的棋盘(右上角为(r,cr,c)),ShenChuanShenChuan从(0,0)出发,每秒能往四个方向运动一格,每隔一段时间就会有一颗导弹落下来,这颗导弹会毁坏降落的方块和相邻4个方块,现在想知道ShenChuanShenChuan能走到离出发点的最远距离(这个点最终不会被导弹炸毁)所需要的最短时间。

输入格式

三个整数$r,c,n(1\leq r \leq500,1\leq c \leq500,1\leq n \leq500)$,表示会降落nn个导弹。

接下来nn行,每行三个整数,xxyytt,第i行表示第i颗导弹在第tit_i秒降落在(xi,yi)(x_i,y_i)

(1x500,1y500,1t500)(1\leq x \leq500,1\leq y \leq500,1\leq t \leq500)

输出格式

仅一行,一个整数,代表答案。

样例

2 2 0
4
2 2 1
1 1 1
0
2 2 1
1 1 2
2
2 2 1
1 1 4
4