题目描述

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

输入格式

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

接下来$n$行，每行三个整数，$x$，$y$，$t$，第i行表示第i颗导弹在第$t_i$秒降落在$(x_i,y_i)$。

$(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