간선도로

시간 제한2초메모리 제한512 MB

요약

H×W 격자에서 가로선 하나와 세로선 하나를 골라 각 칸 주민이 더 가까운 선까지 내는 거리의 합을 최소로 만든다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 누적 합, 수학
정답자: 아직 제출이 없습니다

문제

JOI 시는 동서 방향으로 곧게 뻗은 도로 $H$ 개와 남북 방향으로 곧게 뻗은 도로 $W$ 개로 바둑판 모양으로 나뉘어 있다. 나란히 놓인 두 도로 사이의 간격은 모두 $1$ 이다. JOI 시는 이 $H+W$ 개의 도로 중에서 동서 방향 도로 하나와 남북 방향 도로 하나, 모두 $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$ 개를 고르는 모든 방법을 놓고, 전체 주민이 부담하는 값의 합이 가장 작을 때 그 합을 구하라.

입력

입력은 표준 입력으로 다음 형식에 맞춰 주어진다.

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

첫째 줄에 $H$ 와 $W$ 가 공백으로 구분되어 주어진다. 이어지는 $H$ 개의 줄 중 $i$ 번째 줄에는 $A_{i,1}, A_{i,2}, \dots, A_{i,W}$ 가 공백으로 구분되어 주어진다.

출력

전체 주민이 부담하는 값의 합이 가장 작을 때 그 합을 한 줄에 출력한다.

제한

$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$ )

예제3

예제 1
입력
```
3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
```
예상 출력
```
8
```

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

예상 출력

예제 3
입력
```
2 2
0 0
0 0
```
예상 출력
```
0
```