시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2491118551.829%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

31
W3sicHJvYmxlbV9pZCI6IjEyMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzBcdWMwYzFcdWM2MDhcdWNlMjEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY1NFx1ZDU1OVx1Yzc3NCBcdWMyZWJcdWM1YjRcdWMxMWMgXHVjOWMwXHVhZDZjXHVhY2ZjXHVkNTU5XHVjNzQ0IFx1YWNmNVx1YmQ4MFx1ZDU1YyBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVhZTMwXHVjMGMxXHVjNjA4XHVjZTIxXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDQgXHViOWUxXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWUzMFx1YzBjMVx1YzYwOFx1Y2UyMVx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHViNDE4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc0MCBOJnRpbWVzO01cdWM5ZGNcdWI5YWMgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzc0XHVhY2UwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNlNzhcdWI5YzhcdWIyZTQgXHVhZTMwXHVjMGMxXHVjNjA4XHVjZTIxXHVjNzQ0IFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzQ0IFx1YzgwMVx1YjJmOVx1ZDc4OCBcdWIwOThcdWIyMjBcdWMxMWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwIFx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgXHVhZDZjXHVhYzA0IFx1YzkxMSBcdWM3OTFcdWM1YzVcdWMyZGNcdWFjMDRcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWFjZjNcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVjNzkxXHVjNWM1XHViN2M5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHViMDk4XHViMjA0XHViMjk0IFx1YWUzMFx1YzkwMFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YWMwMFx1Yjg1Y1x1YzEyMFx1YWNmYyBcdWMxMzhcdWI4NWNcdWMxMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjA5OFx1YjIwNFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWMxMzhcdWI4NWMgXHVjNWVkXHVjMmRjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljNCBcdWFkNmNcdWFjMDRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViMjk0IFx1YjA5OFx1YjIwNFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOTA0XHVjNWQwXHViMjk0IG4sIG0sIHIsIHMoMSAmbGU7IHIgJmx0OyBuICZsZTsgMTgsIDEgJmxlOyBzICZsdDsgbSAmbGU7IDE4KSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIG4sIG1cdWM3NDAgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjXHVkMDZjXHVhZTMwLCByLCBzXHViMjk0IFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVjMjE4LCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWI0YTRcdWI4NWNcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U3OFx1Yzc0NCBcdWM2MDhcdWNlMjFcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzJkY1x1YWMwNFx1Yzc0MCAyLDAwMCwwMDBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcmlkIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbWFwIG9mIEJ5dGVsYW5kIGlzIGRyYXduIG9uIGEgZ3JpZCBvZiBzaXplIG4gJnRpbWVzOyBtIChuIGlzIHRoZSB2ZXJ0aWNhbCBkaW1lbnNpb24sIG0gaXMgdGhlIGhvcml6b250YWwgZGltZW5zaW9uKS4gVGhlIGhvcml6b250YWwgbGluZXMgbWFya2luZyB0aGUgZGl2aXNpb24gYXJlIGNhbGxlZCBwYXJhbGxlbHMsIGFuZCBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIG4sIHdoaWxlIHRoZSB2ZXJ0aWNhbCBsaW5lcyBvZiB0aGUgZGl2aXNpb24gYXJlIGNhbGxlZCBtZXJpZGlhbnMsIGFuZCBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIG0gKHNlZSBmaWd1cmUgb24gdGhlIG5leHQgcGFnZSkuPFwvcD5cclxuXHJcbjxwPldlYXRoZXIgZm9yZWNhc3RpbmcgaXMgYSBzZXJpb3VzIGlzc3VlIGluIEJ5dGVsYW5kLiBGb3IgZWFjaCB1bml0IHNxdWFyZSBvZiB0aGUgZ3JpZCBhIGNlcnRhaW4gYW1vdW50IG9mIGNvbXB1dGF0aW9uIHRpbWUgaXMgcmVxdWlyZWQgdG8gcHJlcGFyZSB0aGUgZm9yZWNhc3QuIER1ZSB0byB0ZXJyYWluIGNvbmRpdGlvbnMgYW5kIG90aGVyIGZhY3RvcnMgdGhpcyB0aW1lIG1heSB2YXJ5IGZyb20gc3F1YXJlIHRvIHNxdWFyZS4gVW50aWwgdmVyeSByZWNlbnRseSB0aGUgZm9yZWNhc3Rpbmcgc3lzdGVtIHdhcyBwcm9jZXNzaW5nIHRoZSB1bml0IHNxdWFyZXMgb25lIGFmdGVyIGFub3RoZXIsIHNvIGl0IHRvb2sgYXMgbG9uZyBhcyB0aGUgc3VtIG9mIGFsbCB0aGUgdW5pdCB0aW1lcyB0byBwcmVwYXJlIHRoZSBjb21wbGV0ZSBmb3JlY2FzdC48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgYmVlbiBhc2tlZCB0byBkZXNpZ24gYSBuZXcgc3lzdGVtLCBydW5uaW5nIG9uIGEgbXVsdGlwcm9jZXNzb3IgY29tcHV0ZXIuIFRvIHNoYXJlIHRoZSBjb21wdXRhdGlvbnMgYW1vbmcgcHJvY2Vzc29ycywgdGhlIGFyZWEgb2YgQnl0ZWxhbmQgc2hvdWxkIGJlIGRpdmlkZWQgYnkgciBwYXJhbGxlbHMgYW5kIHMgbWVyaWRpYW5zIGludG8gKHIgKyAxKShzICsgMSkgc21hbGxlciByZWN0YW5nbGVzLiBFYWNoIHByb2Nlc3NvciB3aWxsIGNvdmVyIG9uZSByZWN0YW5nbGUgb2YgdGhpcyBkaXZpc2lvbiBhbmQgd2lsbCBwcm9jZXNzIHRoZSBzcXVhcmVzIG9mIHRoaXMgcmVjdGFuZ2xlIG9uZSBhZnRlciBhbm90aGVyLiBUaGlzIHdheSB0aGUgY29tcHV0YXRpb24gdGltZSBmb3Igc3VjaCByZWN0YW5nbGUgd2lsbCBiZSB0aGUgc3VtIG9mIGFsbCBjb21wdXRhdGlvbiB0aW1lcyBvZiB0aGUgdW5pdCBzcXVhcmVzIGNvbnRhaW5lZCBpbiB0aGlzIHJlY3RhbmdsZS4gVGhlIGNvbXB1dGF0aW9uIHRpbWUgb2YgdGhlIGNvbXBsZXRlIGZvcmVjYXN0IHdpbGwgYmUgdGhlIG1heGltdW0gYW1vbmcgY29tcHV0YXRpb24gdGltZXMgb2YgdGhlIGluZGl2aWR1YWwgcHJvY2Vzc29ycy48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIG1pbmltYWwgcG9zc2libGUgY29tcHV0YXRpb24gdGltZSBmb3Igc29tZSBjaG9pY2Ugb2YgciBwYXJhbGxlbHMgYW5kIHMgbWVyaWRpYW5zLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0sIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIG1hcCBvZiBCeXRlbGFuZCwgdGhlIHJlcXVpcmVkIG51bWJlciBvZiBwYXJhbGxlbHMgYW5kIG1lcmlkaWFucyBhbmQgdGhlIHVuaXQgY29tcHV0YXRpb24gdGltZXMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQsPFwvbGk+XHJcblx0PGxpPmZpbmRzIHRoZSBtaW5pbWFsIHRpbWUgcmVxdWlyZWQgdG8gY29tcHV0ZSB0aGUgY29tcGxldGUgZm9yZWNhc3QsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb2J0YWluZWQgdmFsdWUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGZvdXIgaW50ZWdlcnMgbiwgbSwgciBhbmQgcywgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgKDEgJmxlOyByICZsdDsgbiAmbGU7IDE4LCAxICZsZTsgcyAmbHQ7IG0gJmxlOyAxOCkuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWluIHRoZSBjb21wdXRhdGlvbiB0aW1lcyBvZiB0aGUgdW5pdCBzcXVhcmVzLiBUaGUgai10aCBudW1iZXIgaW4gdGhlIChpICsgMSktc3QgbGluZSBpcyBjPHN1Yj5pLGo8XC9zdWI+ICZtZGFzaDsgdGhlIHRpbWUgcmVxdWlyZWQgdG8gcHJlcGFyZSB0aGUgd2VhdGhlciBmb3JlY2FzdCBmb3IgdGhlIHVuaXQgc3F1YXJlIGxvY2F0ZWQgYmV0d2VlbiB0aGUgKGkgJm1pbnVzOyAxKS1zdCBhbmQgaS10aCBwYXJhbGxlbCBhbmQgYmV0d2VlbiB0aGUgKGogJm1pbnVzOyAxKS1zdCBhbmQgai10aCBtZXJpZGlhbiAoMSAmbGU7IGkgJmxlOyBuLCAxICZsZTsgaiAmbGU7IG0sIDAgJmxlOyBjPHN1Yj5pLGo8XC9zdWI+ICZsZTsgMiAwMDAgMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIHdyaXRlIGV4YWN0bHkgb25lIGxpbmUuIEl0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG9wdGltYWwgY29tcHV0YXRpb24gdGltZS48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lMDMyMGM1NS0yNmQxLTRhNzktYjAxMS01ZDU2YTNiZGZmYzVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI1OHB4OyBoZWlnaHQ6IDIzMXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgMi1uZCBhbmQgNC10aCBwYXJhbGxlbCBhbmQgdGhlIDQtdGggbWVyaWRpYW4gZGl2aWRlIHRoZSBjb3VudHJ5IGludG8gNiByZWN0YW5nbGVzIHdpdGggY29tcHV0YXRpb24gdGltZXMgMjEsIDEzLCAyNywgMjcsIDE3LCAzMS4gVGhlIGNvbXB1dGF0aW9uIHRpbWUgb2YgdGhlIGNvbXBsZXRlIGZvcmVjYXN0IGlzIDMxLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 5번