구역 분할

N×M 격자의 각 칸에 연산 시간이 적혀 있다. 가로선 r개와 세로선 s개를 그어 (r+1)×(s+1)개의 직사각형 구역으로 나눈다.

각 구역의 연산 시간 합 중 최댓값을 최소화하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, r, s가 공백으로 구분되어 주어진다. (1 ≤ r < N ≤ 18, 1 ≤ s < M ≤ 18) 둘째 줄부터 N개의 줄에 M개의 음이 아닌 정수가 주어진다.

출력

가능한 최소 최댓값을 출력한다.

입출력 예시

입력 1

7 8 2 1
5 1 3 2 4 3 3 3
1 5 4 5 2 3 2 1
5 3 3 2 4 5 3 5
3 3 4 5 1 4 3 4
4 4 3 5 2 5 4 5
5 4 4 3 3 2 3 5
4 4 3 2 5 3 3 3

출력 1

31