题目描述

在游戏世界中，给定一个 $M$ * $N$ 的网格，其中每个单元格都填有数字，数字大小表示覆盖能量强度。灰色网格代表禁地，橙色网格代表能量覆盖区域，绿色网格代表生命之树，绿色网格内数字大小表示该生命之树散发的能量的初始强度。 已知每个网格内的能量强度每向外(上下左右)传播一格，能量强度减 $1$，最小减为 $0$ 。

表示无信号，如下图示。当某个位置可以同时接收到多棵生命之树的能量时，取其中接收能量强度的最大值作为该位置的能量强度，对于给定网格，请判断是否存在一条路径，使得从左上角移动到右下角过程中能量不中断，只能上下左右移动。假设接吸收的能量强度低于门限 $Th$ ，能量就会中断。

注意:出发点固定在网格的左上角，终点是网格的右下角。

输入

第一行输入能量强度 $Th$ 。( $1 \le Th \le 100$)

第二行输入矩阵 $M$ 、$N$ 。($1 \le M \le 100，1\le N \le100$)

第三行输入生命之树的个数 $K$。 ($1 \le K \le 100$)

后续 $K$ 行输入生命之树的位置及初始能量强度。(前两个值表示生命之树所在行、列索引，第 $3$ 个值表示生命之树初始能量强度)

输出

返回信号不中断的最短路径，不存在返回 $0$。

样例1

输入

1
4 4
2
0 1 2
3 2 3

输出

6

说明

1. 能量强度门限 $Th$ = $1$

2. $M$ = $4$,$N$ = $4$

3. $4$ * $4$ 网格中一共包含 $2$ 棵生命之树

4. $2$ 棵生命之树的位置，其中第 $1$ 个生命之树在第 $0$ 行第 $1$ 列、初始能量强度 = $2$ ；第 $2$ 棵生命之树在第 $3$ 行第 $2$ 列、初始能量强度 = $3$

image.png

样例2

输入

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

输出

8

说明

1. 能量强度门限 $Th$ = $1$
2. $M$ = $5$ , $N$ = $5$
3. $5$ * $5$ 网格中一共包含 $5$ 棵生命之树
4. $5$ 棵生命之树的位置，其中第 $1$ 棵生命之树在第 $0$ 行第 $1$ 列、初始能量强度 = $2$:第 $2$ 棵生命之树在第 $0$ 行第 $4$列、初始能量强度 =$3$;第 $3$ 棵生命之树在第 $2$ 行第 $3$ 列、初始能量强度 = $2$ ;第 $4$ 棵生命之树在第 $4$ 行第 $0$ 列 、初始能量强度 $3$ ;第 $5$ 棵生命之树在第 $4$ 行第 $3$ 列、初始能量强度= $2$;

image.png

注：如上Grid ，绿色表示生命之树，橙色为生命之树散发的能量往外传播后覆盖的区域，按照途中箭头方向移动路径最短。