| Codeforces Round 719 (Div. 3) |
|---|
| Закончено |
Дима проспал будильник, который должен был поднять его в школу.
Диме интересно, успеет ли он прийти на первый урок. Для этого ему необходимо узнать минимальное время, которое потребуется ему, чтобы дойти от дома до школы.
Город, в котором живет Дима, представляет собой прямоугольное поле размером $$$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
Пояснение к первому примеру:
