题目描述

牛为什么要过马路？

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

31

提示

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