기상 예측

선영이는 N x M 격자로 나뉜 지역의 기상 예측을 맡았다. 각 칸에는 그 칸을 예측하는 데 걸리는 시간이 적혀 있다.

선영이는 격자에 정확히 r개의 가로선과 정확히 s개의 세로선을 그어 격자를 나눌 수 있다. 이렇게 나누면 격자는 (r + 1) x (s + 1)개의 직사각형 구역으로 나뉘며, 각 구역의 작업은 동시에 진행할 수 있다.

따라서 전체 작업 시간은 나뉜 구역들 중 칸의 시간 합이 가장 큰 구역의 값이 된다. 이 최댓값이 가능한 한 작아지도록 나눌 때, 그 값을 구하시오.

첫째 줄에 네 정수 n, m, r, s가 주어진다 (1 <= r < n <= 18, 1 <= s < m <= 18). n과 m은 격자의 크기이고, r은 가로로 나누는 선의 개수, s는 세로로 나누는 선의 개수이다.

다음 n개의 줄에는 각 줄마다 m개의 정수가 주어진다. 각 정수는 0 이상 2,000,000 이하이다.

기상 예측 작업을 끝내는 데 필요한 시간의 최솟값을 출력한다.