간선도로

문제

JOI 시는 동서 방향으로 곧게 뻗은 $H$ 개의 도로와, 남북 방향으로 곧게 뻗은 $W$ 개의 도로에 의해 바둑판 모양으로 구획되어 있다. 도로와 도로 사이의 간격은 $1$ 이다. JOI 시에서는 이 $H+W$ 개의 도로 중에서 동서 방향으로 $1$ 개, 남북 방향으로 $1$ 개, 합계 $2$ 개의 도로를 간선도로로 선택하게 되었다.

북쪽에서 $i$ 번째 ($1\,\le\,i\,\le\,H$) 도로와 서쪽에서 $j$ 번째 ($1\,\le\,j\,\le\,W$) 도로의 교차점을 교차점 $(i,j)$ 라고 하자. 교차점 $(i,j)$ 와 북쪽에서 $m$ 번째 ($1\,\le\,m\,\le\,H$) 도로의 거리는 $|i-m|$ 이고, 교차점 $(i,j)$ 와 서쪽에서 $n$ 번째 ($1\,\le\,n\,\le\,W$) 도로의 거리는 $|j-n|$ 이다. 또한 교차점 $(i,j)$ 근처에는 $A_{i,j}$ 명의 주민이 살고 있다.

$2$ 개의 간선도로를 선택했을 때, JOI 시의 모든 주민에 대한, 가장 가까운 교차점에서 더 가까운 쪽의 간선도로까지의 거리의 총합의 최솟값을 구하시오.

제한

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

서브태스크

서브태스크 1 [10점]

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

서브태스크 2 [90점]

• 추가 제약이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$H$ $W$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,W}$
:
$A_{H,1}$ $A_{H,2}$ ... $A_{H,W}$

출력
JOI 시의 모든 주민에 대한, 가장 가까운 교차점에서 더 가까운 쪽의 간선도로까지의 거리의 총합의 최솟값을 출력한다.

예제 입력 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