#P0835. 梦魇轮回

梦魇轮回

题目描述

故地重游,小白凝望着那块斑驳的回忆板,陷入了一场无尽的梦境,过往的回忆化作梦魇正在吞噬小白残存的记忆。

在这片梦境中,回忆板上的誓言早已支离破碎,曾经温暖的拥抱化作冷冽的幻象。梦境与梦魇交织,爱与痛轮回不息,小白被困于此。 每一段痛苦都像是时光的枷锁,每一次轮回都消耗着小白的理智,你是否能帮助小白从这场宿命般的梦境中挣脱?

梦境被抽象为一个 n×mn \times m 的矩阵,每个格子代表一段回忆,并带有一个整数“痛苦值”。 矩阵中的格子有下面几种:

  • 痛苦的回忆:痛苦值为正整数,表示通过该格子时必须付出的痛苦代价。
  • 美好的回忆:痛苦值为00,只要小白到达任意一个这样的格子(美好的的回忆可以有多个),就能立即离开梦境。
  • 传送门:痛苦值为负数−p-p,表示如果选择使用该传送门,则需付出代价 pp,不使用则无需付出代价。通过传送门可以瞬间抵达任意其他传送门,传送花费仅计算起点传送门的代价,与目标传送门无关。如果不使用,则经过该格子不产生代价。

小白从矩阵的左上角(1,1)(1, 1)出发,每次只能向右或下移动(除非使用传送门)。每经过一个格子(除传送门),必须付出对应的痛苦值作为代价(包括起点),如果使用传送门,也要付出对应的代价。

同时,小白的san值有限,在一次轮回中,如果累计付出代价超过上限 kk,小白会死亡并进入下一次轮回。

你的目标是帮助小白从起点(1,1)(1, 1)出发,找到离开梦境的最小代价。

输入格式

第一行输入三个整数$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)$,k(1≤k≤109)k(1 \le k \le 10^9),分别表示矩阵的行数、列数和小白能承受代价的上限。

接下来nn行,每行输入mm个整数,表示矩阵中每个格子的痛苦值ai,j(−109≤ai,j≤109)a_{i, j}( -10^9\le a_{i, j} \le 10^9)。

输出格式

输出一个整数,表示小白从起点(1,1)(1, 1)出发离开梦境的最小总代价;如果无论如何都无法在某一次轮回中成功离开梦境,输出−1-1。

样例

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

提示

对于样例11,先一直向右走到位于(1,3)(1, 3)的传送门,花费1+21 + 2,然后花费∣−4∣|-4|传送到位于(3,2)(3, 2)的传送门,向右走到(3,3)(3, 3)离开梦境。

对于样例22,无论如何也无法离开梦境。