题目描述

牛为什么要过马路？

嗯，一个原因是 ${Farmer John }$的农场有很多道路，这使得他的奶牛在不经过许多道路的情况下不可能四处走动。

${FJ}$的农场排列成${N×}$${N}$方格的田地${（3≤}$${N≤}$${100）}$，有${N-1}$条南北路和${N-1}$条东西路穿过农场的内部，作为田 地之间的分隔线。高高的围栏围绕着外围，防止奶牛离开农场。

母牛贝西可以从任何田地自由移动到任何其他相邻的田地（北、东、南或西），只要她在穿过分隔两个田地的马路之前仔细观察两边。过马路需要她 ${T }$单位的时间${（0≤}$${T≤}$${1,000,000）}$。

一天，${FJ }$邀请贝西去他家玩一场友谊赛。

${Bessie }$从西北角的场地开始，${FJ }$的房子在东南角的场地，所以 ${Bessie }$在她前面有很长的路要走。由于她一路上饿了，她每到第三个田地就停下来吃 草（不包括她的起始田地，但可能包括 ${FJ }$房子所在的最后一块田地）。

有些田地比其他田地更草，所以停下来吃饭所需的时间媛决于她停下来的田地。

请帮助 ${Bessie }$确定到达 ${FJ }$家所需的最短时间。

输入格式

第一行输入包含${N}$和${T}$。

接下来的${N}$行中每个都包含${N}$正整数（每个最多${100000}$个），描述了在每个字段吃草所需的时间。

第一行的第一个数字是西北角。

输出格式

打印贝西去${FJ}$家所需的最短时间

样例

输入样例

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

输出样例

31

提示

本例的最佳解决方案包括向东移动${3}$个正方形（吃"${10}$"），然后向南移动两次，向西移动一次（吃"${5}$"），最后向南和向东移动到目标。