迪马睡过了闹钟,而闹钟本应送他去学校。
Dima 想知道他是否有时间来上第一节课。为此,他需要知道从家到学校所需的最短时间。
Dima 居住的城市是一个 $$$n \times m$$$ 大小的矩形区域。该字段中的每个单元格 $$$(i, j)$$$ 由一个数字 $$$a_{ij}$$$ 表示:
- 数字$$$-1$$$表示禁止通过该牢房;
- 数字 $$$0$$$ 表示牢房是空闲的,迪玛可以穿过它。
- 数字 $$$x$$$ ($$$1 \le x \le 10^9$$$) 表示该单元格包含一个成本为 $$$x$$$ 的传送门。具有门户的单元也被认为是免费的。
从任何传送门,Dima 都可以前往任何其他传送门,而从传送门 $$$(i, j)$$$ 移动到传送门 $$$(x, y)$$$ 的时间对应于其成本 $$$a_{ij} + a_{xy}$$$ 的总和。
除了在传送门之间移动之外,Dima 还可以在时间 $$$w$$$ 的一侧相邻的空闲单元格之间移动。特别是,他可以进入带有传送门的牢房而不使用它。
最初,Dima 位于左上角单元格 $$$(1, 1)$$$,学校位于右下角单元格 $$$(n, m)$$$。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$w$$$ ($$$2 \le n, m \le 2 \cdot 10^3$$$, $$$1 \le w \le 10^9$$$),其中 $$$n$$$ 和 $$$m$$$ 是城市大小,$$$w$$$ 是时间迪马在空闲的牢房之间移动。
接下来的 $$$n$$$ 行每行包含 $$$m$$$ 数字 ($$$-1 \le a_{ij} \le 10^9$$$) — 单元格的描述。
保证单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 是空闲的。
输出
输出 Dima 到达学校所需的最短时间。如果他根本无法去学校,则输出“-1”。
示例
输入 #1
5 5 1 0 -1 0 1 -1 0 20 0 0 -1 -1 -1 -1 -1 -1 3 0 0 0 0 -1 0 0 0 0
输出 #1
14
注意
第一个样本的说明: