时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一个 \(N\) 行 \(M\) 列的迷宫，行号从上到下依次为 \(0,1,…,N-1\)，列号从左到右依次为 \(0,1,…,M-1\)。芭比兔的窝在(0,0) 的格子中。这一天她得知一个恐怖消息，迷宫中的一些格子被安装了定时炸弹，其中第 \(i\) 枚炸弹安装在 \(x_i\) 行 \(y_i\) 列的格子中，爆炸的时间为 \(t_i\)，爆炸后包括其上下左右相邻格子都会被炸毁而无法通行。

　　于是芭比兔立即开始逃生，每一个时刻中，她能上下左右移动到相邻的格子中的任意一个，当然格子要没被炸毁才行。如果一个格子在时刻 \(t\) 被炸弹炸毁，那么芭比兔只能在 \(t\) 之前的时刻在这个格子里出现。

　　那么芭比兔最少需要多少时间才能逃离到一个安全的格子。　　

【输入格式】

　　第一行包含三个整数：\(N,M,K\)，其中 \(K\) 表示有 \(K\) 枚定时炸弹。
　　接下来的 \(K\) 行，第 \(i+1\) 行有三个用空格隔开的整数：\(x_i，y_i\) 和 \(t_i\)，表示第 \(i\) 枚定时炸弹位于 \(x_i\) 行 \(y_i\) 列的格子中（\(0≤x_i<N\)，\(0≤y_i<M\)），其爆炸时间为 \(t_i（1≤t_i≤1000）\)。

【输出格式】

　　输出一个整数，即芭比兔逃生所花的最少时间。如果无论如何都无法逃到安全的格子则输出 -1。

【输入输出样例】

　Input

4 5 4
0 0 2
2 1 1
1 1 3
0 3 5

　Output

5

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N,M≤302\)，\(1≤K≤50000\)。

【来源】

　　Mr.he