题目描述

小杰在一个矩阵的左上角，她准备跳到右下角。小杰必须按照象棋的"马"的规则移动，即如果当前的坐标是$(x_0, y_0)$，那么落点的坐标(x, y)必须满足$|x - x_0| + |y - y_0| = 3$且$x ≠ x_0$, $y ≠ y_0$。小杰每跳一步就会收集落点的数字加入到总和里。她想知道最终最小的总和是多少?

输入描述

第一行输入两个正整效n, m，代表矩阵的行数和列数，接下来的n行，每行输入m个正整数aij，代表矩阵的元素。

$1 \leq n, m \leq 800$；

$1 \leq a_{ij} \leq 10^9$。

输出描述

如果无法到达，请输出-1。否则输出一个正整数，代表最终的最小点和。

输入示例

4 4
1 2 3 4
5 6 7 8
9 10 11 12
1 2 3 4

输出示例

12

提示信息

1+7+4=12。

时间限制：c/c++：1s；其他语言：9s。