问题描述

JOI市被划分为$H$条直行的道路和$W$条直行的道路，形成了棋盘的格子形状。道路之间的间隔为$1$。JOI市决定从这$H+W$条道路中选择一条东西方向的道路和一条南北方向的道路，共计$2$条道路作为干线道路。

将从北边数第$i$条道路($1≦i≦H$)和从西边数第$j$条道路($1≦j≦W$)的交叉点记为$(i,j)$。交叉点$(i,j)$到从北边数第$m$条道路($1≦m≦H$)的距离为$|i-m|$，交叉点$(i,j)$到从西边数第$n$条道路($1≦n≦W$)的距离为$|j-n|$。另外，交叉点$(i,j)$附近居住着$A_{i,j}$个居民。

求选择了$2$条干线道路时，对于JOI市所有居民来说，距离最近的交叉点到最近的干线道路的距离总和的最小值。

约束条件

• $2 ≦ H ≦ 25$
• $2 ≦ W ≦ 25$
• $0 ≦ A_{i,j} ≦ 100$ ($1 ≦ i ≦ H$, $1 ≦ j ≦ W$)

输入

输入以以下格式从标准输入中给出。

$H$ $W$ $A_{1,1}$ $A_{1,2}$ ... $A_{1,W}$ : $A_{H,1}$ $A_{H,2}$ ... $A_{H,W}$

输出

输出JOI市所有居民中，距离最近的交叉点到最近的干线道路的距离总和的最小值。

子问题 1 [10分]

• $A_{i,j} = 1$ ($1 ≦ i ≦ H$, $1 ≦ j ≦ W$)

子问题 2 [90分]

• 没有附加限制。

输入示例 1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

输出示例 1

8

例如，选择从北边数第$2$条道路和从西边数第$1$条道路作为干线道路。

输入示例 2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

输出示例 2

164

例如，选择从北边数第$3$条道路和从西边数第$2$条道路作为干线道路。