Ферма Джона представляет собой решётку из n * n квадратных полей, и n − 1 дороги "север-юг" и n − 1 дороги "запад-восток", проходящих внутри фермы и служащих разделителями между полями. Высокий забор вокруг фермы по её внешнему периметру, препятствует выходу коров за пределы фермы. Беси может свободно перемещаться с любого поля на любое соседнее поле (на север, юг, запад, восток). Ей требуется t единиц времени на переход дороги.

Однажды ФД пригласил Беси посетить его дом поиграть в шахматы. Беси начинает с северо-западного углового поля фермы, а дом ФД находится на южно-восточном углу поля. Поскольку Беси становится голодной во время пути, она останавливается на каждом третьем поле, которое посетит, поесть траву (не включая стартовое поле, но включая возможно финальное поле, где расположен дом ФД). Некоторые поля травянистее, чем другие, поэтому количество времени, которое она потратит на еду на поле, зависит от поля, на котором она остановилась.

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

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

Первая строка содержит n (3 ≤ n ≤ 100) и t (0 ≤ t ≤ 106). Каждая из следующих n строк содержит n положительных целых чисел (каждое не более 105), описывающих количество времени, требуемое чтобы съесть траву на каждом поле. Первое число в первой строке это северо-западный угол.

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

Выведите минимальное количество времени, которое требуется Беси чтобы добраться до дома ФД.

Пояснение

Оптимальное решение в этом примере включает движение на восток на 3 клетки (едим 10), затем двигаемся два раза на юг и один раз на восток, (едим 5), и, наконец, на юг и на восток к цели.