Дима проспал будильник, который должен был поднять его в школу.
Диме интересно, успеет ли он прийти на первый урок. Для этого ему необходимо узнать минимальное время, которое потребуется ему, чтобы дойти от дома до школы.
Город, в котором живет Дима, представляет собой прямоугольное поле размером \(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)\).
Выходные данные
Выведите одно число — минимальное время, которое потребуется Диме, чтобы добраться до школы. Если он не сможет добраться до школы вообще — выведите «-1».