J8 实践-5 拯救王妃

题目描述

一个 $M\times N$ 的矩形格子，王妃被关在其中一个格子中，王子正赶来拯救王妃。 王子从左上角的格子$(1,1)$出发,每个格子中都有绑匪，王子要花费一定的时间把绑匪消灭才能从这个格子接着进行下一步。每个格子中的绑匪被消灭所花时间不一定相同。一旦王子消灭了某个格子中的绑匪，他就可以向上下左右四个方向去移动。 绑匪头目知道王子在途中，他设了一个定时炸弹，在 $T$ 秒后将会爆炸，告诉你王妃的位置和每个格子中绑匪被消灭的时间。你得任务是计算王子是否在 $T$ 时间限制内赶到王妃的位置。 例如：这是一个 $4 \times 3$ 的矩形格子的描述，数字表示消灭绑匪的时间。

2 3 2
2 5 1
5 3 1
3 1 1

假设王妃在$(4,2),T=10$,这就没办法在 $10$ 秒时间拯救王妃；但如果 $T=15$,王子就在可以成功赶到王妃的位置，并且还有 $4$ 秒的剩余时间，方法如下：从 $(1,1)$ 出发，向右移到 $(1,2)$，然后到 $(1,3)$,一直下到 $(4,3)$，然后向左移到 $(4,2)$,一共花了 $11$ 秒（注意：王子一定要把王妃所在位置的绑匪也消灭）。

输入格式

第一行包含两个整数 $M$ 和 $N$ ，分别表示行和列。 接下来 $M$ 行，每行 $N$ 个整数，表示消灭绑匪的时间。 最后一行是三个整数 $a,b,T$，其中 $(a,b)$ 是王妃被困的位置，$T$ 是定时炸弹设的期限。

输出格式

如果王子不可能在 $T$ 秒赶去救王妃则输出“ $NO$ ”； 否则输出两行，第一行输出 “ $YES$ ”，第二行输出最大的剩余时间。

样例输入

4 3 
2 3 2
2 5 1
5 3 1
3 1 1
4 2 15

样例输出

YES
4

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有：$1\leq N,M \le 70$ 。