#4992. [Usaco2017 Feb]Why Did the Cow Cross the Road

内存限制:256 MiB 时间限制:10 Sec

题目描述

有一幅n*n的方格图,n <=100,每个点上有一个值。
\从(1,1)出发,走到(n,n),只能走上下左右。
每走一步花费t,每走三步需要花费走完三步后到达格子的值。
求最小花费的值。

输入格式

输出格式

样例

样例输入


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

样例输出


			
31

数据范围与提示