시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 39 16 13 50.000%

문제

화학이 싫어서 지구과학을 공부한 선영이가 기상예측을 하는 일을 맡게 되었다.

선영이가 기상예측을 해야 되는 지역은 N*M짜리 격자판이고 각각의 칸마다 기상예측을 하는데 걸리는 시간이 있다.

이때 선영이는 이 격자판을 적당히 나눠서 각각의 구간의 작업을 동시에 할 수 있는데 그러므로 나누어진 구간 중 작업시간의 합이 최대인 곳을 최소화 한다면 선영이의 작업량이 최소가 될 것이다. 이때 나누는 기준은 주어진 개수의 가로선과 세로선을 이용해서 나누면 된다.

가로로 나눌 수 있는 선의 개수가 주어지고 세로 역시 주어진다고 할 때 나누어진 구간의 합의 최대를 최소로 하는 나누는 방법을 구하라.

입력

첫줄에는 n, m, r, s(1<=r<n<=18, 1<=s<m<=18) 가 주어지는데 n, m은 지역의 가로, 세로크기, r, s는 가로로 나누는 수, 세로로 나누는 수를 의미한다. 그 뒤로는 각각의 칸을 예측하는데 걸리는 시간이 주어진다(2000000이하)

출력

선영이가 결과를 구하는데 걸리는 최소의 시간을 출력한다.

예제 입력

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

예제 출력

31

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 5번