CF1520G.To Go Or Not To Go?

Dima overslept the alarm clock, which was supposed to raise him to school.

Dima wonders if he will have time to come to the first lesson. To do this, he needs to know the minimum time it will take him to get from home to school.

The city where Dima lives is a rectangular field of $n \times m$ size. Each cell $(i, j)$ on this field is denoted by one number $a_{ij}$:

• The number $-1$ means that the passage through the cell is prohibited;
• The number $0$ means that the cell is free and Dima can walk though it.
• The number $x$ ($1 \le x \le 10^9$) means that the cell contains a portal with a cost of $x$. A cell with a portal is also considered free.

From any portal, Dima can go to any other portal, while the time of moving from the portal $(i, j)$ to the portal $(x, y)$ corresponds to the sum of their costs $a_{ij} + a_{xy}$.

In addition to moving between portals, Dima can also move between unoccupied cells adjacent to one side in time $w$. In particular, he can enter a cell with a portal and not use it.

Initially, Dima is in the upper-left cell $(1, 1)$, and the school is in the lower right cell $(n, m)$.

季马睡过头了，没能听到本该叫他去上学的闹钟。

季马想知道他能否及时赶到第一节课堂。为此，他需要知道从家到学校所需的最短时间。

季马所居住的城市是一个大小为 $n \times m$ 的矩形网格。该网格中每个单元格 $(i, j)$ 用一个整数 $a_{ij}$ 表示：

• 数字 $-1$ 表示该单元格禁止通行；
• 数字 $0$ 表示该单元格为空闲状态，季马可以自由通过；
• 数字 $x$（其中 $1 \le x \le 10^9$）表示该单元格中存在一个传送门，其使用代价为 $x$；含有传送门的单元格同样被视为可通行。

从任意一个传送门出发，季马均可直接传送到任意其他传送门，且从传送门 $(i, j)$ 传送到传送门 $(x, y)$ 所需时间为二者代价之和：$a_{ij} + a_{xy}$。

除传送门外，季马还可花费时间 $w$ 在相邻（上下左右四邻）的空闲单元格之间移动。特别地，他可以进入一个含传送门的单元格但选择不使用该传送门。

初始时，季马位于左上角单元格 $(1, 1)$，而学校位于右下角单元格 $(n, m)$。

The first line contains three integers $n$, $m$ and $w$ ($2 \le n, m \le 2 \cdot 10^3$, $1 \le w \le 10^9$), where $n$ and $m$ are city size, $w$ is time during which Dima moves between unoccupied cells.

The next $n$ lines each contain $m$ numbers ($-1 \le a_{ij} \le 10^9$) — descriptions of cells.

It is guaranteed that the cells $(1, 1)$ and $(n, m)$ are free.

第一行包含三个整数 $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)$ 是空闲的。

Output the minimum time it will take for Dima to get to school. If he cannot get to school at all, then output "-1".

输出迪马到达学校所需的最短时间。如果他根本无法到达学校，则输出“-1”。

Explanation for the first sample:

第一个样例的解释：