과수원 Batch 컴파일 명령

승현이와 상수는 의형제로서 부자인 석환이가 운영하는 넓은 과수원에서 몇 년 동안 같이 일해 왔습니다. 이 과수원에는 나무들이 $n \times m$ 크기의 배열 형태로 심어져 있습니다. 승현이는 사과나무를 심어 왔고 상수는 배나무를 심어 왔습니다. 그러나, 이 형제들은 체계적으로 일을 하지는 않아서 나무들은 사과나무들이 배 나무 사이에 있는 등 이상하게 심어져 있습니다. 배열의 각 칸에는 나무가 정확히 한 그루 심어져 있습니다.

그러던 중 석환이가 돈이 안 되는 과수원 사업에서 돈을 더 잘 벌 수 있는 부동산 투기로 눈을 돌리기로 했습니다. 그 이전에 석환이는 승현이와 상수의 노고를 치하하여 과수원의 소유권을 이 두 사람에게 넘겨주기로 합니다. 석환이는 둘을 불러 우선 승현이에게 과수원 전체의 소유권을 넘기고, 과수원 내부의 어떤 직사각형 영역을 하나 잘라낸 뒤, 이 영역 안의 나무들의 소유권은 상수에게 넘겨주라고 하더니 떠나버렸습니다. 법 지식이 거의 없는 승현이와 상수는 땅을 나눈 이후의 모든 처리는 변호사에게 맡기기로 했습니다.

승현이는 사과 나무 모두를 소유하고 싶고 상수은 모든 배나무를 소유하고 싶지만, 어떤 나무도 옮겨 심고 싶지는 않습니다. 그들이 변호사에게 이렇게 이야기하자, 변호사는 몇 개의 나무들의 소유권을 바꿀(승현->상수, 상수->승현) 수 있으나, 한 그루의 소유권을 바꾸는 데 1달러를 받겠다고 했습니다. 따라서 이 둘은 변호사에게 돈을 최대한 적게 주기 위해서 직사각형을 적절히 선택해야 합니다.

다음 그림들은 세 가지 예제를 보여주는데, 0과 1은 각각 사과나무 한 그루와 배나무 한 그루를 의미합니다.

[그림 1]에서 가장 좋은 방법은 검정색 직사각형 안에 있는 4열의 나무들을 잘라 내서 상수에게 주는 것입니다. 그러면 두 그루의 소유권만 바꿔주면 됩니다. (한 그루는 승현이로부터 상수에게, 또다른 한 그루는 상수에서부터 승현이에게) 따라서 비용은 2달러입니다.

[그림 2]에서 가장 좋은 방법은 검정색 직사각형 안의 (테두리 바로 안쪽) 부분을 잘라 6그루의 소유권을 바꿔주는 것입니다. 비용은 6달러입니다.

[그림 3]에서 가장 좋은 방법은 3그루의 배나무를 포함하는 직사각형 영역을 잘라낸 뒤 가장 오른쪽에 위치한 배나무의 소유권을 상수에게 넘기는 것입니다. 이 때 비용은 1달러가 됩니다. 이 방법 외에도 비용이 1달러가 되도록 직사각형을 잘라내는 경우가 존재합니다.

입력 형식

첫 번째 줄에는 과수원의 크기를 나타내는 두 정수 $n$과 $m$이 주어집니다. 다음 $n$개 줄에는 $m$개의 숫자가 들어옵니다. 이 중 $i$행 $j$열의 숫자가 0이면 해당 칸에 사과 나무가 심어져 있는 것이고, 1이면 해당 칸에 배나무가 심어져 있는 것입니다.

출력 형식

첫 번째 줄에 최소한의 비용을 출력합니다.

서브태스크

1. (4점) $n = 1$, $2 \le m \le 20$
2. (4점) $n = 1$, $2 \le m \le 15,000$
3. (5점) $n = 1$, $2 \le m \le 1,000,000$
4. (3점) $1 \le n \le 2$, $2 \le m \le 100,000$
5. (4점) $1 \le n \le 150$, $2 \le m \le 150$
6. (5점) $1 \le n \le 150$, $2 \le m \le 5,000$

예제