문제
JOI 시는 동서로 곧게 뻗은 도로 \(H\)개와 남북으로 곧게 뻗은 도로 \(W\)개로 바둑판처럼 나뉘어 있다. 도로와 도로 사이 간격은 \(1\)이다. 이 \(H+W\)개의 도로 가운데 동서 방향 \(1\)개, 남북 방향 \(1\)개, 모두 \(2\)개를 간선 도로로 고르기로 했다. 북쪽에서 \(i\)번째 (\(1 \le i \le H\)) 도로와 서쪽에서 \(j\)번째 (\(1 \le j \le W\)) 도로가 만나는 곳을 교차점 \((i,j)\)라 한다. 교차점 \((i,j)\)와 북쪽에서 \(m\)번째 도로의 거리는 \(|i-m|\)이고, 서쪽에서 \(n\)번째 도로의 거리는 \(|j-n|\)이다. 교차점 \((i,j)\) 근처에는 주민이 \(A_{i,j}\)명 산다. 간선 도로 \(2\)개를 골랐을 때, 모든 주민에 대해 가장 가까운 교차점에서 더 가까운 쪽 간선 도로까지의 거리의 합이 최소가 되도록 하고 싶다. 그 최솟값을 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(A_{1,1}\) \(A_{1,2}\) \(\cdots\) \(A_{1,W}\)
\(\vdots\)
\(A_{H,1}\) \(A_{H,2}\) \(\cdots\) \(A_{H,W}\)
- 첫째 줄에 동서 도로의 수 \(H\)와 남북 도로의 수 \(W\)가 공백 하나로 구분되어 주어진다.
- 다음 \(H\)줄의 \(i\)번째 줄에 \(W\)개의 정수 \(A_{i,1}, A_{i,2}, \ldots, A_{i,W}\)가 공백 하나로 구분되어 주어진다.
- \(2 \le H \le 25\)
- \(2 \le W \le 25\)
- \(0 \le A_{i,j} \le 100\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 모든 주민에 대한, 가장 가까운 교차점에서 더 가까운 쪽 간선 도로까지의 거리 합의 최솟값을 출력한다.
예시 1
입력
3 5
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
출력
164