#P0835. 梦魇轮回
梦魇轮回
题目描述
故地重游,小白凝望着那块斑驳的回忆板,陷入了一场无尽的梦境,过往的回忆化作梦魇正在吞噬小白残存的记忆。
在这片梦境中,回忆板上的誓言早已支离破碎,曾经温暖的拥抱化作冷冽的幻象。梦境与梦魇交织,爱与痛轮回不息,小白被困于此。 每一段痛苦都像是时光的枷锁,每一次轮回都消耗着小白的理智,你是否能帮助小白从这场宿命般的梦境中挣脱?
梦境被抽象为一个 的矩阵,每个格子代表一段回忆,并带有一个整数“痛苦值”。 矩阵中的格子有下面几种:
- 痛苦的回忆:痛苦值为正整数,表示通过该格子时必须付出的痛苦代价。
- 美好的回忆:痛苦值为,只要小白到达任意一个这样的格子(美好的的回忆可以有多个),就能立即离开梦境。
- 传送门:痛苦值为负数,表示如果选择使用该传送门,则需付出代价 ,不使用则无需付出代价。通过传送门可以瞬间抵达任意其他传送门,传送花费仅计算起点传送门的代价,与目标传送门无关。如果不使用,则经过该格子不产生代价。
小白从矩阵的左上角出发,每次只能向右或下移动(除非使用传送门)。每经过一个格子(除传送门),必须付出对应的痛苦值作为代价(包括起点),如果使用传送门,也要付出对应的代价。
同时,小白的san值有限,在一次轮回中,如果累计付出代价超过上限 ,小白会死亡并进入下一次轮回。
你的目标是帮助小白从起点出发,找到离开梦境的最小代价。
输入格式
第一行输入三个整数$n, m(1 \le n \le 2 \times 10^5, 1 \le m \le 2 \times 10^5, 1 \le n \times m \le 2 \times 10^5)$,,分别表示矩阵的行数、列数和小白能承受代价的上限。
接下来行,每行输入个整数,表示矩阵中每个格子的痛苦值。
输出格式
输出一个整数,表示小白从起点出发离开梦境的最小总代价;如果无论如何都无法在某一次轮回中成功离开梦境,输出。
样例
3 3 9
1 2 -4
4 9 5
8 -3 0
7
3 3 7
5 3 0
-1 7 2
1 2 -3
-1
提示
对于样例,先一直向右走到位于的传送门,花费,然后花费传送到位于的传送门,向右走到离开梦境。
对于样例,无论如何也无法离开梦境。