Ферма Джона представляет собой решётку из \(N \times N\) квадратных
полей (\(3 \leq N \leq 100\)), и \(N-1\) дороги "север-юг" и \(N-1\) дороги
"запад-восток", проходящих внутри фермы и служащих разделителями между
полями. Высокий забор вокруг фермы по её внешнему периметру, препятствует
выходу коров за пределы фермы. Беси может свободно перемещаться с любого
поля на любое соседнее поле (на север, юг, запад, восток). Ей требуется
\(T\) единиц времени на переход дороги (\(0 \leq T \leq 1,000,000\)).
Однажды ФД пригласил Беси посетить его дом поиграть в шахматы.
Беси начинает с северо-западного углового поля фермы, а дом ФД находится
на южно-восточном углу поля. Поскольку Беси становится голодной во время
пути, она останавливается на каждом третьем поле, которое посетит,
поесть траву (не включая стартовое поле, но включая возможно финальное
поле, где расположен дом ФД). Некоторые поля травянистее, чем другие,
поэтому количество времени, которое она потратит на еду на поле, зависит
от поля, на котором она остановилась.
Помогите Беси определить минимальное количество времени, которое
может ей потребоваться, чтобы добраться до дома ФД.
ФОРМАТ ВВОДА (файл visitfj.in):
Первая строка ввода содержит \(N\) и \(T\). Каждая из следующих \(N\) строк
содержит \(N\) положительных целых чисел (каждое не более 100,000), описывающих
количество времени, требуемое чтобы съесть траву на каждом поле. Первое число
в первой строке это северо-западный угол.
ФОРМАТ ВВОДА (файл visitfj.out):
Выведите минимальное количество времени, которое требуется Беси чтобы
добраться до дома ФД.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
|
31
|