브라우니 자르기

Bessie가 직사각형 브라우니를 구웠다. 이 브라우니는 작은 브라우니 정사각형들로 이루어진 $R \times C$ 격자로 볼 수 있다($1 \le R \le 500$, $1 \le C \le 500$). $i$행 $j$열 칸에는 초콜릿 칩이 $N_{ij}$개 들어 있다($0 \le N_{ij} \le 4000$).

Bessie는 브라우니를 $A \times B$개의 덩어리로 나누어 $A \times B$마리의 소에게 하나씩 주려고 한다($1 \le A \le R$, $1 \le B \le C$). 자르는 방법은 다음과 같다. 먼저 정수 좌표를 따라 가로로 $A-1$번 잘라 브라우니를 $A$개의 가로 띠로 나눈다. 그다음 각 띠를 독립적으로 세로로 $B-1$번 잘라(역시 정수 경계에서) 각 띠를 $B$조각으로 만든다. 이렇게 하면 전체 $A \times B$개의 조각이 생긴다.

그 후 $A \times B - 1$마리의 소가 각자 조각을 하나씩 골라 가고, 마지막 조각이 Bessie에게 남는다. 소들은 욕심이 많아 초콜릿 칩이 가장 적게 든 조각을 Bessie에게 남긴다.

Bessie가 최적으로 자른다고 할 때, 자신이 확실히 받을 수 있는 초콜릿 칩 개수의 최댓값을 구하여라.

예를 들어 칩이 다음과 같이 분포한 $5 \times 4$ 브라우니를 생각하자.

1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

여기서 $A = 4$, $B = 2$이므로 Bessie는 브라우니를 가로 띠 4개로 나누고 각 띠를 두 조각으로 잘라야 한다. 예를 들어 다음과 같이 자를 수 있다.

1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

이렇게 하면 모든 조각이 초콜릿 칩을 최소 3개씩 가지므로, 욕심 많은 소들이 먼저 조각을 가져가도 Bessie에게는 3개가 남는다.

• 첫째 줄: 공백으로 구분된 네 정수 $R$, $C$, $A$, $B$.
• 둘째 줄부터 $R+1$째 줄까지: $i+1$째 줄에는 $C$개의 정수 $N_{i1}, \ldots, N_{iC}$가 공백으로 구분되어 주어진다.

• 첫째 줄: Bessie가 자신의 조각으로 확실히 받을 수 있는 초콜릿 칩 개수의 최댓값을 나타내는 정수 하나.