Page not loading? Try clicking here.
Placeholder

#8362
Subtask

주요 도로 1s 1024MB

Problems

정올 도시는 동서 방향으로 평행하게 무한히 뻗어 있는 H개의 도로와 남북 방향으로 평행하게 무한히 뻗어 있는 W개의 도로로 이루어진 격자 형태의 도로망을 가지고 있다. 도로와 도로 사이의 간격은 1이다. 정올 도시에서는 이 H+W개의 도로 중에서 동서 방향 도로 1개와 남북 방향 도로 1개, 총 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)}명의 주민이 거주하고 있다.

동서 방향 도로 1개와 남북 방향 도로 1개, 총 2개의 주요 도로를 선택했을 때, 정올 도시의 모든 주민이 주요 도로까지 이동해야 하는 거리의 총합의 최솟값을 구하여라.

다시 요약하자면, 정올 도시는 H개의 동서 방향 도로와 W개의 남북 방향 도로로 구성된 격자 형태의 도로망을 가지고 있고, 각 교차점에는 A_{(i,j)}명의 주민이 거주하며, 두 주요 도로(동서 방향 1개, 남북 방향 1개)를 선택할 때, 각 주민이 거주하는 교차점에서 주요 도로까지 이동해야 하는 거리가 발생한다. 문제는 모든 주민의 이동 거리 총합이 최소가 되도록 주요 도로를 선택하는 것이다.


Input

입력은 다음 형식으로 표준 입력을 통해 주어진다.

H W

A_({1,1)} A_({1,2)} ... A_({1,W)}

...

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

[제한]
2 ≦ H ≦ 25
2 ≦ W ≦ 25
0 ≦ A_{(i,j)} ≦ 100 (1 ≦ i ≦ H, 1 ≦ j ≦ W)


Output

정올 도시의 모든 주민이 해당 교차점에서 가장 가까운 주요 도로까지 이동하는 거리의 총합의 최솟값을 출력하라.


Subtask

# Score Condition
#130

모든 A_{(i,j)} = 1 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

#270

추가 제약 조건 없음


Example #1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
8

예를 들어, 북쪽에서 2번째 도로와 서쪽에서 1번째 도로를 주요 도로로 선택하면 된다.


Example #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

만약 북쪽에서 1번째 도로와 서쪽에서 1번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 582가 된다.

만약 북쪽에서 2번째 도로와 서쪽에서 2번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 225가 된다.

만약 북쪽에서 3번째 도로와 서쪽에서 2번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 164가 된다.



Source

JOI 2018 예선

You must sign in to write code.