You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

有一个$r×c$的棋盘（右上角为($r,c$)），$ShenChuan$从(0,0)出发，每秒能往四个方向运动一格，每隔一段时间就会有一颗导弹落下来，这颗导弹会毁坏降落的方块和相邻4个方块。

现在想知道$ShenChuan$能走到离出发点的最远距离所需要的最短时间。

Input Format

三个整数$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)$

Output Format

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

Sample

输入样例1

2 2 0

输出样例1

4

输入样例2

2 2 1
1 1 1

输出样例2

0

Hint

$1\leq r \leq500,1\leq c \leq500,1\leq n \leq500$

$1\leq x \leq500,1\leq y \leq500,1\leq t \leq500$