Чому корова перейшла дорогу (Золото)#10538
Ферма Фермера Джона являє собою квадратну сітку розміром n \times n полів. Всередині ферми проходять n - 1 доріг з півночі на південь та n - 1 доріг зі сходу на захід, що розділяють сусідні поля. По периметру ферми встановлено високу огорожу, яка не дозволяє коровам покинути ферму. Корова Бессі може вільно переміщатися з будь-якого поля на будь-яке сусіднє поле (на північ, схід, південь або захід), якщо перед переходом через дорогу, що розділяє два поля, вона уважно подивиться в обидва боки. Перехід через одну дорогу займає в неї одиниць часу.
Одного разу Фермер Джон запрошує Бессі до себе додому, щоб зіграти дружню партію в шахи. Бессі починає свій шлях з поля, розташованого в північно-західному куті, а дім Фермера Джона знаходиться в полі в південно-східному куті, тому на Бессі чекає доволі довгий шлях. По дорозі вона зголодніє і зупиняється, щоб поїсти трави, на кожному третьому полі, яке вона відвідує (початкове поле не враховується, але останнім полем, на якому вона зупиниться, може виявитися поле з домом Фермера Джона). Деякі поля вкриті травою краще за інші, тому час, необхідний Бессі для зупинки та поїдання трави, залежить від поля, на якому вона зупиняється.
Допоможіть Бессі визначити мінімальний час, за який вона зможе дістатися до дому Фермера Джона.
У першому рядку містяться n~(3 \le n \le 100) та t~(0 \le t \le 10^6). У наступних рядках містяться по додатних цілих чисел (кожне не перевищує 10^5), що описують час, необхідний для поїдання трави на кожному полі. Перше число першого рядка відповідає полю в північно-західному куті.
Виведіть мінімальний час, необхідний Бессі, щоб дістатися до дому Фермера Джона.
У цьому прикладі оптимальний маршрут полягає в тому, щоб пройти на схід поля і з'їсти траву, що займає одиниць часу, потім пройти два поля на південь і одне поле на схід і з'їсти траву, що займає одиниць часу, і, нарешті, пройти одне поле на південь і одне поле на схід, досягнувши мети.
Приклад 1