U196955 [小翔系列水题] 毛笋

刚吃完早饭，小翔肚子有点饿了。他准备去野外采集一些毛笋。

这 $K$ 个毛笋都在一个 $N\cdot M$ 的平面上，第 $i$ 个毛笋的坐标为 $(X_i,Y_i)$ ，小翔在 $(1,1)$ ，厨房在 $(N,M)$ 。 小翔很厉害，一眼就看出了每一个毛笋的坐标和高度 $H_i$ ，并且采集毛笋不需要时间，但是前提是必须得走到毛笋的坐标上。小翔每秒可以往上下左右四个方向中的任意一个方向走一格。 由于地心引力的原因，毛笋每秒都会下沉一个单位长度。当高度下沉为 $0$ 或 $0$ 以下时，小翔就采集不到了。小翔想采集到尽可能**多**的毛笋，但他又不想太累。请你求出他在最快到达厨房的条件下能采集到的**最多**的毛笋。

输入共 $K+1$ 行。 第一行三个正整数 $N,M,K$ 分别表示厨房的坐标和毛笋的数量。 接下来 $K$ 行，第 $i$ 行三个正整数 $X_i,Y_i,H_i$ 分别表示第 $i$ 个毛笋的横坐标，纵坐标和初始高度。

输出共两行。 第一行输出小翔最快到达厨房需要的时间，如果你不会请输出 $-1$ 。 第二行输出小翔能采集到的**最多**的毛笋，如果你不会请输出 $-1$。 第一小问答对 $20\%$ ，第二小问答对 $80\%$。

### 样例解释 对于样例1，竹笋分布如下图 $x$ 表示小翔，$e$ 表示厨房，数字表示毛笋高度，$'.'$ 表示空地。 ``` . . . . e . . . 8 . . 9 4 . . 3 . . . . x 4 . . . ``` 先向上走一格，采集一个毛笋 变为： ``` . . . . e . . . 7 . . 8 3 . . x . . . . . 3 . . . ``` 向上，再向右，采集第二个毛笋 ``` . . . . e . . . 5 . . x 1 . . . . . . . . 1 . . . ``` 再往右，可是这是这个毛笋**已经缩到地下去了，所以没有采集到毛笋**。 再往右，再往上，采集到第三个毛笋。 ``` . . . . e . . . x . . . -2 . . . . . . . . -2 . . . ``` 再往右，再往上，到达厨房。 综上，总路径为（路径不唯一）：  总共用 $8$ 步，采集到 $3$ 个毛笋。可以证明没有更优解。 对于样例2，采集不到毛笋，空手回家 :( 。 ### 数据范围 对于 $20\%$ 的数据，满足 $N,M,K\leq 10$。 对于 $60\%$ 的数据，满足 $N,M,K\leq 5\times10^3$。 对于 $100\%$ 的数据，满足 $1\leq N,M,K\leq 10^6, 1\leq H_i\leq 10^9, K\leq N\times M-2, 1\leq X_i\leq N,1\leq Y_i\leq M$。 保证在 $(1,1)$ 和 $(N,M)$ 没有毛笋，没有两个毛笋在同一坐标。 ### 温馨提示 本题输入量较大，请采用比较快速的读入方式读取数据。 大样例见附件下载。