1195: 方格图

有一幅$n*n$的方格图，每个点上有一个值 $a_{i,j}$。

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

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

求最小花费的值。

第一行两个整数 $n$ 和 $t$。

接下来 $n$ 行，每行 $n$ 个数，代表方格图上的值。

输出一行一个整数，表示最小花费的值。

4 2

30 92 36 10

38 85 60 16

41 13 5 68

20 97 13 80

31

提示

对于样例，先向右走三步（额外花费“10”），再向下走两步，又向左走了一步（额外花费“5”），最后向下走一步，再向右走一步到达终点，总共时间是15（额外花费）+16=31

对于 $100\%$的数据，$3\le n \le 100,0 \le t \le 1000000,1\le a_{i,j} \le 100000$。

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！