题目描述
小白在n×mn \times mn×m的迷宫中走路，小白从迷宫起点(1,1)(1,1)(1,1)出发，且小白仅能向下和向右走，从 (i,j)→(i+1,j)(i,j) \rightarrow (i+1,j)(i,j)→(i+1,j) 或者 从 (i,j)→(i,j+1)(i,j) \rightarrow (i,j+1)(i,j)→(i,j+1) 。 迷宫中每个方格有一个权值ai,ja_{i,j}ai,j,小白初始拥有一个体力值hhh，每走到一个方格便会扣除该方格上的权值,如果hhh被扣除到000以下(≤0)(\leq 0)(≤0) 时 ，小白就失败了（走到终点时体力小于等于000也被认为失败）。有先见之明的小白从小黑那里偷学了一种恢复魔法，可以完全恢复在一格内消耗的权值，即在 (i,j)(i,j)(i,j) 格使用这次魔法，这个方格不再消耗血量。
然而小白并不希望依赖过多次魔法，先请你求出令小白顺利到达迷宫终点时(n,m)(n,m)(n,m)，小白使用的最小魔法次数。
输入
第一行有3个整数nnn，mmm (0≤n×m≤3×103)(0 \leq n \times m \leq 3 \times 10^3)(0≤n×m≤3×103)，hhh (0<h≤103)(0 < h \leq 10^3)(0<h≤103) 分别表示n×mn \times mn×m大小的迷宫和小白的初始体力。
接下来nnn行每行mmm个整数。
a1,1a_{1,1}a1,1 a1,2a_{1,2}a1,2 a1,3a_{1,3}a1,3 a1,...a_{1,...}a1,... a1,ma_{1,m}a1,m
a2,1a_{2,1}a2,1 a2,2a_{2,2}a2,2 a2,3a_{2,3}a2,3 a2,...a_{2,...}a2,... a2,ma_{2,m}a2,m
...
an,1a_{n,1}an,1 an,2a_{n,2}an,2 an,3a_{n,3}an,3 an,...a_{n,...}an,... an,ma_{n,m}an,m
0≤aij≤10000 \leq a_{ij} \leq 10000≤aij≤1000
初始位置 (1,1)(1,1)(1,1) 默认为 000 ，即初始位置不消耗体力。
输出
输出一个整数表示小白使用的最小魔法次数
样例输入 Copy
2 3 4
0 4 6
3 5 1
样例输出 Copy
2