魔法
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小白在n \times m的迷宫中走路，小白从迷宫起点(1,1)出发，且小白仅能向下和向右走，从 (i,j) \rightarrow (i+1,j) 或者 从 (i,j) \rightarrow (i,j+1) 。 迷宫中每个方格有一个权值a_{i,j},小白初始拥有一个体力值h，每走到一个方格便会扣除该方格上的权值,如果h被扣除到0以下(\leq 0) 时 ，小白就失败了（走到终点时体力小于等于0也被认为失败）。有先见之明的小白从小黑那里偷学了一种恢复魔法，可以完全恢复在一格内消耗的权值，即在 (i,j) 格使用这次魔法，这个方格不再消耗血量。
然而小白并不希望依赖过多次魔法，先请你求出令小白顺利到达迷宫终点时(n,m)，小白使用的最小魔法次数。

输入描述:

第一行有3个整数n，m (0 \leq n \times m \leq 3 \times 10^3)，h (0 < h \leq 10^3) 分别表示n \times m大小的迷宫和小白的初始体力。
接下来n行每行m个整数。
a_{1,1} a_{1,2} a_{1,3} a_{1,...} a_{1,m}
a_{2,1} a_{2,2} a_{2,3} a_{2,...} a_{2,m}
...
a_{n,1} a_{n,2} a_{n,3} a_{n,...} a_{n,m}
0 \leq a_{ij} \leq 1000
初始位置 (1,1) 默认为 0 ，即初始位置不消耗体力。

输出描述:

输出一个整数表示小白使用的最小魔法次数
示例1

输入

复制 
2 3 4
0 4 6
3 5 1

输出

复制 
2
示例2

输入

复制 
4 4 5
0 2 3 4
1 2 0 1
3 4 2 2
3 4 3 4

输出

复制 
2