문제

JOI 시는 동서로 뻗어있는 H개의 도로와 남북으로 뻗어있는 W개의 도로에 의해 바둑판 형태로 구획되어 있습니다. 도로와 도로 사이 간격은 1입니다. JOI 시는 H+W개의 도로 중 동서로 뻗어있는 도로 1개, 남북으로 뻗어있는 도로 1개 총 2개를 간선 도로로 지정하려 합니다.

위에서 i(1 <= i <= H)번째 도로와 왼쪽에서 j(j <= i <= H)번째 도로의 교차점을 (i, j)라 합시다. 교차점 (i, j)와 위에서 m(1 <= m <= H)번째 도로의 거리는 |i-m|이고, 교차점 (i, j)와 왼쪽에서 n(1 <= n<= W)번째 도로의 거리는 |j-n|입니다. 또 교차점 (i, j)의 근처에는 A_{i, j}명의 주민이 살고 있습니다.

두 개의 간선 도로를 지정할 때, JOI 시의 모든 주민에 대해 가장 가까운 교차점에서 간선 도로까지 거리의 합의 최솟값을 구합시다.

입력

표준 입력이 아래와 같은 형식으로 주어집니다.

(형식 참조)

출력

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