Чому корова перейшла дорогу (Золото)

Ферма Джона складається з ґратки розміром n на n квадратних полів, розділених n − 1 дорогами, що йдуть з півночі на південь, і n − 1 дорогами, що йдуть із заходу на схід. Ці дороги розташовані всередині ферми і служать роздільниками між полями. Високий паркан навколо ферми не дозволяє коровам виходити за її межі. Бессі може вільно переміщатися з одного поля на сусіднє (на північ, південь, захід або схід), витрачаючи t одиниць часу на перетин дороги.

Одного разу Джон запросив Бессі до себе додому пограти в шахи. Бессі починає свій шлях з північно-західного кута ферми, а дім Джона знаходиться на південно-східному куті. Під час подорожі Бессі стає голодною, тому вона зупиняється на кожному третьому полі, яке відвідує, щоб поїсти траву (не враховуючи стартове поле, але враховуючи можливе фінальне поле, де знаходиться дім Джона). Деякі поля мають більше трави, ніж інші, тому час, який вона витрачає на їжу, залежить від конкретного поля.

Допоможіть Бессі визначити мінімальний час, необхідний для того, щоб дістатися до дому Джона.

Вхідні дані

Перший рядок містить n (3 ≤ n ≤ 100) і t (0 ≤ t ≤ 10^6). Кожен з наступних n рядків містить n додатних цілих чисел (кожне не більше 10^5), що описують час, необхідний для поїдання трави на кожному полі. Перше число в першому рядку відповідає північно-західному куту.

Вихідні дані

Виведіть мінімальний час, який потрібен Бессі, щоб дістатися до дому Джона.

Приклади

Примітка

Оптимальний маршрут у цьому прикладі включає рух на схід на 3 клітинки (їмо 10), потім два рази на південь і один раз на схід (їмо 5), і, нарешті, на південь і на схід до цілі.