题目描述

奶牛们为什么要穿马路？一个原因只是因为 FJ 的牧场的路实在是太多了，使得奶牛们每天不得不穿梭在许许多多的马路中央。

FJ的牧场可以看作是一块 $N\times N$ 的田地（$3\le N\le 100$），$N-1$ 条南北向的道路和 $N-1$ 条东西向的道路贯穿整个牧场，同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。Bessie只要穿过分离两块田野的道路，就可以从任何田野移动到与其相邻的田野里去（北，东，南或西）。当然，Bessie穿过每一条马路都是需要$T$ 时间的。（$0\le T\le 1,000,000$）

有一天，FJ 邀请 Bessie来他家下棋，Bessie 从牧场的西北角出发，FJ 的家在牧场的东南角。因为 Bessie 在中途可能会饿，所以她每走过三块田野就要停下来，享用她所在田野上的新鲜的牧草（不包括 Bessie 的出发点，但是可能会包括终点 FJ 的家），牧场上有些田野的牧草长得比其他地方茂盛，所以Bessie 对应的停留时间也会变长。

请帮帮 Bessie 计算出她走到 FJ 家的最短时间。

输入格式

接下来 $N$ 行，每行 $N$ 个数表示每块田野Bessie需要停留的时间（每块最多不超过$100,000$），第一行的第一块田野是牧场的西北角

输出格式

一行一个整数表示Bessie走到FJ家的最短时间

样例 #1

样例输入 #1

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

样例输出 #1

31

提示

对于样例，Bessie 先向东走过了三块田野（在“ $10$ ”停留），再向南走两步，又向西走了一步（在“ $5$ ”停留），最后向南走一步，再向东走一步到达FJ的家（不用停留），总共时间是 $15（停留时间）+16（穿马路时间）=31$