题目描述

有一幅$n\times n$的方格图，每个点上有一个值。

从$(1,1)$出发，走到$(n,n)$，只能走上下左右。

每走一步花费$t$，每走三步需要花费走完三步后到达格子的值。

求最小花费的值。

输入格式

第一行包含一个整数$N$;

接下来$N+1$行,每行$n$个整数。

输出格式

一个整数：最小花费的值。

样例

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

31

数据规模与约定

对于$100\%$的数据：$n\le 100$.