G. Идти или не идти?
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дима проспал будильник, который должен был поднять его в школу.

Диме интересно, успеет ли он прийти на первый урок. Для этого ему необходимо узнать минимальное время, которое потребуется ему, чтобы дойти от дома до школы.

Город, в котором живет Дима, представляет собой прямоугольное поле размером $$$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)$$$.

Входные данные

В первой строке содержатся три целых числа $$$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)$$$ свободны.

Выходные данные

Выведите одно число — минимальное время, которое потребуется Диме, чтобы добраться до школы. Если он не сможет добраться до школы вообще — выведите «-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
Выходные данные
14
Примечание

Пояснение к первому примеру: