행렬분할 2

$n \times m$ 크기의 행렬이 있다. 이 행렬을 가로로 $a$번, 세로로 $b$번 잘라 $(a + 1) \times (b + 1)$ 개의 부분으로 분할하려고 한다. 이때 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함하지 않는 부분은 존재할 수 없다.

그림 1	그림 2

그림 1과 같은 $6 \times 7$ 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다.

분할의 '점수'는 잘라진 각 부분의 합들 중에서 가장 큰 값으로 정의한다. 예를 들어, 그림 2와 같은 분할에서의 점수는 색칠한 부분의 합인 19이다. 최소로 분할하면 점수는 15이고, 그림은 생략한다.

행렬이 주어졌을 때 가능한 최소 점수를 구하는 프로그램을 작성하시오.

첫 번째 줄에 자연수 $n(2 \le n \le 100)$과 $m(2 \le m \le 8)$이 주어진다. 두 번째 줄에는 자연수 $a(1 \le a < n)$, $b(1 \le b < m)$가 주어진다. 세 번째 줄부터 $n$개의 줄에 걸쳐 행렬의 원소들이 공백으로 구분되어 주어진다. 행렬의 모든 원소는 100,000 이하의 자연수이다.

첫 번째 줄에 최소 점수를 출력한다.