UOJ Logo

NOI.AC

1S 512MB

#1599. 绝地大逃生

Statistics

题目描述

在一个 $n \times m$ 的矩形地图上,$Mas$位于其中一个点。地图上每个格子有加血的药剂,和掉血的火焰,药剂的药效不同,火焰的大小也不同,每个格子上有一个数字,如果格子上的数字是正数说明是一个药剂代表增加的生命值,如果是负数说明是火焰代表失去的生命值。

$Mas$初始化有 $v$ 点血量,他的血量上限是 $c$,任何时刻他的生命值都不能大于血量上限,如果血量为 $0$ 则会死亡,不能继续游戏。

矩形地图上的四个角$(1,1),(1,m),(n,1),(n,m)$为游戏的出口。游戏中只要选定了一个出口,就必须朝着这个方向走。例如,选择了左下的出口,就只能往左和下两个方向前进,选择了右上的出口,就只能往右和上两个方向前进,左上和右下方向的出口同理。

如果成功逃生,那么剩余生命值越高,则游戏分数越高。为了能拿到最高分,请你帮忙计算如果成功逃生最多能剩余多少血量,如果不能逃生输出 $−1$。

输入格式

第一行依次输入整数 $n,m,x,y,v,c(1 < n,m \leq 1000,1 \leq x \leq n,1 \leq y \leq m,1 \leq v \leq c \leq 10000)$, 其中 $n, m$ 代表地图大小,$(x, y)$ 代表$Mas$的初始位置,$v$ 代表$Mas$的初始化血量,$c$代表$Mas$的生命值上限。

接下来 $n$ 行,每行有 $m$ 个数字,代表地图信息。(每个数字的绝对值不大于$100$,地图中$Mas$的初始位置的值一定为 $0$)

输出格式

一行输出一个数字,代表成功逃生最多剩余的血量,如果失败输出 $−1$。

样例输入

4 4 3 2 5 10
1 2 3 4
-1 -2 -3 -4
4 0 2 1
-4 -3 -2 -1

样例输出

10