시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 78 46 34 66.667%

문제

플로브디브의 유명한 초콜릿 가공업자 Bonny는 가로 M개, 세로 N개의 격자에 건포도들이 들어있는, N*M크기의 건포도 초콜릿을 만들었다. 각 1*1 격자에는 최소 1개 이상의 건포도가 들어있으며, 2개 이상의 격자를 가로질러서 존재하는 건포도는 없다.

초기에, 초콜릿은 하나의 거대한 단일 블록으로 이루어져 있고, Bonny는 이 초콜릿을 N*M개의 단일 블록으로 나눠야 한다. Bonny는 굉장히 바쁘기 때문에 욕심쟁이 Peter에게 이 일을 맡기려고 한다. Peter는 직사각형 전체를 일직선으로 자르는 행동만 할 수 있으며, 한번 자를때마다 그에 따른 보상을 요구한다.

Bonny는 수중에 돈이 없지만 남은 건포도가 상당하기 때문에 Peter에게 돈 대신 건포도를 지불하려 한다. 욕심쟁이 Peter는 이 제안을 동의했지만, "초콜릿 한 조각을 작은 두 조각으로 자를 때마다, 초기 큰 초콜릿에 있었던 건포도의 개수만큼의 수입을 받아야 한다" 는 조건을 걸었다.

Bonny는 Peter에게 최소한의 건포도를 주려 한다. Bonny는 각 조각에 있는 건포도의 수를 알며, Peter가 잘라야 하는 건포도의 조각이나 위치 모두 Bonny가 결정할 수 있다. Bonny가 지불해야 하는 건포도의 최소 양을 구하여라.

입력

표준 입력으로부터 다음의 데이터를 읽어야 한다 :

  • 첫번째 줄에는 건포도의 크기 N,M이 주어진다.
  • 이후 N개 줄에 M개의 정수 Rij가 주어진다. 이는 i행 j열에 있는 건포도의 수이다.
  • 1 <= N,M <= 50
  • 1 <= Ri,j <= 1000

출력

Bonny가 주어야 하는 건포도의 양의 최솟값을 출력한다.

예제 입력 1

2 3
2 7 5
1 9 5

예제 출력 1

77

힌트

다음과 같이 자르면 77개의 건포도를 주고 초콜릿을 자를 수 있다.

W3sicHJvYmxlbV9pZCI6IjU0NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzRcdWQzZWNcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3JhaXNpbnMucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE3MXB4OyB3aWR0aDoyNTJweFwiIFwvPlx1ZDUwY1x1Yjg1Y1x1YmUwY1x1YjUxNFx1YmUwY1x1Yzc1OCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjZDA4XHVjZjVjXHViOWJmIFx1YWMwMFx1YWNmNVx1YzVjNVx1Yzc5MCBCb25ueVx1YjI5NCBcdWFjMDBcdWI4NWMgTVx1YWMxYywgXHVjMTM4XHViODVjIE5cdWFjMWNcdWM3NTggXHVhY2E5XHVjNzkwXHVjNWQwIFx1YWM3NFx1ZDNlY1x1YjNjNFx1YjRlNFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQsIE4qTVx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjNzRcdWQzZWNcdWIzYzQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVhYzAxIDEqMSBcdWFjYTlcdWM3OTBcdWM1ZDBcdWIyOTQgXHVjZDVjXHVjMThjIDFcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWM3NFx1ZDNlY1x1YjNjNFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWM3M2NcdWJhNzAsIDJcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWNhOVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWI4NWNcdWM5YzhcdWI3ZWNcdWMxMWMgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWM3NFx1ZDNlY1x1YjNjNFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QwOFx1YWUzMFx1YzVkMCwgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMmU4XHVjNzdjIFx1YmUxNFx1Yjg1ZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBCb25ueVx1YjI5NCBcdWM3NzQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IE4qTVx1YWMxY1x1Yzc1OCBcdWIyZThcdWM3N2MgXHViZTE0XHViODVkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIyMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIEJvbm55XHViMjk0IFx1YWQ0OVx1YzdhNVx1ZDc4OCBcdWJjMTRcdWMwNThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzY5NVx1YzJlY1x1YzdjMVx1Yzc3NCBQZXRlclx1YzVkMFx1YWM4YyBcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1YjllMVx1YWUzMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFBldGVyXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM4MDRcdWNjYjRcdWI5N2MgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1Yzc5MFx1Yjk3NFx1YjI5NCBcdWQ1ODlcdWIzZDlcdWI5Y2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1Y1x1YmM4OCBcdWM3OTBcdWI5N2NcdWI1NGNcdWI5YzhcdWIyZTQgXHVhZGY4XHVjNWQwIFx1YjUzMFx1Yjk3OCBcdWJjZjRcdWMwYzFcdWM3NDQgXHVjNjk0XHVhZDZjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5Cb25ueVx1YjI5NCBcdWMyMThcdWM5MTFcdWM1ZDAgXHViM2M4XHVjNzc0IFx1YzVjNlx1YzljMFx1YjljYyBcdWIwYThcdWM3NDAgXHVhYzc0XHVkM2VjXHViM2M0XHVhYzAwIFx1YzBjMVx1YjJmOVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgUGV0ZXJcdWM1ZDBcdWFjOGMgXHViM2M4IFx1YjMwMFx1YzJlMCBcdWFjNzRcdWQzZWNcdWIzYzRcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVjNjk1XHVjMmVjXHVjN2MxXHVjNzc0IFBldGVyXHViMjk0IFx1Yzc3NCBcdWM4MWNcdWM1NDhcdWM3NDQgXHViM2Q5XHVjNzU4XHVkNTg4XHVjOWMwXHViOWNjLCAmcXVvdDtcdWNkMDhcdWNmNWNcdWI5YmYgXHVkNTVjIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM3OTFcdWM3NDAgXHViNDUwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWM3OTBcdWI5N2MgXHViNTRjXHViOWM4XHViMmU0LCBcdWNkMDhcdWFlMzAgXHVkMDcwIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1YzVkMCBcdWM3ODhcdWM1YzhcdWIzNTggXHVhYzc0XHVkM2VjXHViM2M0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWMyMThcdWM3ODVcdWM3NDQgXHViYzFiXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNCZxdW90OyBcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YWM3OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Qm9ubnlcdWIyOTQgUGV0ZXJcdWM1ZDBcdWFjOGMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YWM3NFx1ZDNlY1x1YjNjNFx1Yjk3YyBcdWM4ZmNcdWI4MjQgXHVkNTVjXHViMmU0LiBCb25ueVx1YjI5NCBcdWFjMDEgXHVjODcwXHVhYzAxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjNzRcdWQzZWNcdWIzYzRcdWM3NTggXHVjMjE4XHViOTdjIFx1YzU0Y1x1YmE3MCwgUGV0ZXJcdWFjMDAgXHVjNzk4XHViNzdjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjNzRcdWQzZWNcdWIzYzRcdWM3NTggXHVjODcwXHVhYzAxXHVjNzc0XHViMDk4IFx1YzcwNFx1Y2U1OCBcdWJhYThcdWI0NTAgQm9ubnlcdWFjMDAgXHVhY2IwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIEJvbm55XHVhYzAwIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzc0XHVkM2VjXHViM2M0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM1OTFcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWIyZTRcdWM3NGNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Yzc3ZFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQgOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzc0XHVkM2VjXHViM2M0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOLE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgTlx1YWMxYyBcdWM5MDRcdWM1ZDAgTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggUmlqXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IGlcdWQ1ODkgalx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzc0XHVkM2VjXHViM2M0XHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+MSAmbHQ7PSBOLE0gJmx0Oz0gNTA8XC9saT5cclxuXHQ8bGk+MSAmbHQ7PSBSaSxqICZsdDs9IDEwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkJvbm55XHVhYzAwIFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzc0XHVkM2VjXHViM2M0XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yzc5MFx1Yjk3NFx1YmE3NCA3N1x1YWMxY1x1Yzc1OCBcdWFjNzRcdWQzZWNcdWIzYzRcdWI5N2MgXHVjOGZjXHVhY2UwIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWM3OTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3JhaXNpbnMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjgycHg7IHdpZHRoOjcxMXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmFpc2lucyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcmFpc2lucy5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTcxcHg7IHdpZHRoOjI1MnB4XCIgXC8+UGxvdmRpdiZyc3F1bztzIGZhbW91cyBtYXN0ZXIgY2hvY29sYXRpZXIgQm9ubnkgbmVlZHMgdG8gY3V0IGEgc2xhYiBvZiBjaG9jb2xhdGUgd2l0aCByYWlzaW5zLiBUaGUgY2hvY29sYXRlIGlzIGEgcmVjdGFuZ3VsYXIgYmxvY2sgb2YgaWRlbnRpY2FsIHNxdWFyZSBwaWVjZXMuIFRoZSBwaWVjZXMgYXJlIGFsaWduZWQgd2l0aCB0aGUgZWRnZXMgb2YgdGhlIGNob2NvbGF0ZSwgYW5kIHRoZXkgYXJlIGFycmFuZ2VkIGluIE4gcm93cyBhbmQgTSBjb2x1bW5zLCBmb3IgYSB0b3RhbCBvZiBOKk0gcGllY2VzLiBFYWNoIHBpZWNlIGhhcyBvbmUgb3IgbW9yZSByYWlzaW5zIG9uIGl0LCBhbmQgbm8gcmFpc2lucyBsaWUgYmV0d2VlbiBvciBhY3Jvc3MgcGllY2VzLjxcL3A+XHJcblxyXG48cD5Jbml0aWFsbHksIHRoZSBjaG9jb2xhdGUgaXMgb25lIHNpbmdsZSwgbW9ub2xpdGhpYyBibG9jay4gQm9ubnkgbmVlZHMgdG8gY3V0IGl0IGludG8gc21hbGxlciBhbmQgc21hbGxlciBibG9ja3MgdW50aWwgZmluYWxseSBzaGUgaGFzIGN1dCB0aGUgY2hvY29sYXRlIGRvd24gdG8gaXRzIE4qTSBpbmRpdmlkdWFsIHBpZWNlcy4gQXMgQm9ubnkgaXMgdmVyeSBidXN5LCBzaGUgbmVlZHMgdGhlIGhlbHAgb2YgaGVyIGFzc2lzdGFudCwgU2x5IFBldGVyLCB0byBkbyB0aGUgY3V0dGluZy4gUGV0ZXIgb25seSBtYWtlcyBzdHJhaWdodCBsaW5lLCBlbmQtdG8tZW5kIGN1dHMgYW5kIGhlIHdhbnRzIHRvIGJlIHBhaWQgZm9yIGV2ZXJ5IHNpbmdsZSBjdXQgaGUgbWFrZXMuIEJvbm55IGhhcyBubyBtb25leSBhdCBoYW5kLCBidXQgc2hlIGhhcyBwbGVudHkgb2YgcmFpc2lucyBsZWZ0IG92ZXIsIHNvIHNoZSBvZmZlcnMgdG8gcGF5IFBldGVyIGluIHJhaXNpbnMuIFNseSBQZXRlciBhZ3JlZXMgdG8gdGhpcyBhcnJhbmdlbWVudCwgYnV0IHVuZGVyIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uOiBldmVyeSB0aW1lIGhlIGN1dHMgYSBnaXZlbiBibG9jayBvZiBjaG9jb2xhdGUgaW50byB0d28gc21hbGxlciBibG9ja3MsIGhlIGhhcyB0byBiZSBwYWlkIGFzIG1hbnkgcmFpc2lucyBhcyB0aGVyZSBhcmUgb24gdGhlIGJsb2NrIGhlIHdhcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+Qm9ubnkgd2FudHMgdG8gcGF5IFBldGVyIGFzIGxpdHRsZSBhcyBwb3NzaWJsZS4gU2hlIGtub3dzIGhvdyBtYW55IHJhaXNpbnMgdGhlcmUgYXJlIG9uIGVhY2ggb2YgdGhlIE4qTSBwaWVjZXMuIFNoZSBjYW4gY2hvb3NlIHRoZSBvcmRlciBpbiB3aGljaCBzaGUgZ2l2ZXMgUGV0ZXIgYW55IHJlbWFpbmluZyBibG9ja3MsIGFuZCBzaGUgY2FuIGFsc28gdGVsbCBQZXRlciB3aGF0IGN1dHMgdG8gbWFrZSAoaG9yaXpvbnRhbCBvciB2ZXJ0aWNhbCkgYW5kIHdoZXJlIGV4YWN0bHkgdG8gbWFrZSB0aGVtLiBIZWxwIEJvbm55IGRlY2lkZSBob3cgdG8gY3V0IHRoZSBjaG9jb2xhdGUgaW50byBpbmRpdmlkdWFsIHBpZWNlcywgc28gdGhhdCBzaGUgcGF5cyBTbHkgUGV0ZXIgYXMgZmV3IHJhaXNpbnMgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgbnVtYmVyIG9mIHJhaXNpbnMgb24gZWFjaCBvZiB0aGUgaW5kaXZpZHVhbCBwaWVjZXMsIGRldGVybWluZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHJhaXNpbnMgdGhhdCBCb25ueSB3aWxsIGhhdmUgdG8gcGF5IFNseSBQZXRlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBtdXN0IHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dCB0aGUgZm9sbG93aW5nIGRhdGE6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzIE4gYW5kIE0sIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9saT5cclxuXHQ8bGk+VGhlIG5leHQgTiBsaW5lcyBkZXNjcmliZSBob3cgbWFueSByYWlzaW5zIHRoZXJlIGFyZSBvbiBlYWNoIHBpZWNlIG9mIHRoZSBjaG9jb2xhdGUuIFRoZSBrdGggb2YgdGhlc2UgTiBsaW5lcyBkZXNjcmliZXMgdGhlIGt0aCByb3cgb2YgdGhlIGNob2NvbGF0ZS4gRWFjaCBzdWNoIGxpbmUgY29udGFpbnMgTSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gVGhlIGludGVnZXJzIGRlc2NyaWJlIHRoZSBwaWVjZXMgb24gdGhlIGNvcnJlc3BvbmRpbmcgcm93IGluIG9yZGVyIGZyb20gbGVmdCB0byByaWdodC4gVGhlIHB0aCBpbnRlZ2VyIG9uIHRoZSBrdGggbGluZSAoYW1vbmcgdGhlc2UgTiBsaW5lcykgdGVsbHMgeW91IGhvdyBtYW55IHJhaXNpbnMgYXJlIG9uIHRoZSBwaWVjZSBpbiB0aGUga3RoIHJvdyBhbmQgdGhlIHB0aCBjb2x1bW4uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgTiwgTSAmbGU7IDUwIFRoZSBudW1iZXIgb2YgcGllY2VzIG9uIGVhY2ggc2lkZSBvZiB0aGUgY2hvY29sYXRlPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBSayxwICZsZTsgMTAwMCBUaGUgbnVtYmVyIG9mIHJhaXNpbnMgb24gdGhlIHBpZWNlIGluIHRoZSBrdGggcm93IGFuZCB0aGUgcHRoIGNvbHVtbjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3Qgd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2YgcmFpc2lucyB0aGF0IEJvbm55IHdvdWxkIGhhdmUgdG8gcGF5IFNseSBQZXRlci4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+T25lIHBvc3NpYmxlIHdheSAob3V0IG9mIG1hbnkpIHRvIGFjaGlldmUgYSBjb3N0IG9mIDc3IGlzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3JhaXNpbnMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjgycHg7IHdpZHRoOjcxMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBjdXQgdGhhdCBCb25ueSBhc2tzIFBldGVyIHRvIG1ha2Ugc2VwYXJhdGVzIHRoZSB0aGlyZCBjb2x1bW4gZnJvbSB0aGUgcmVzdCBvZiB0aGUgY2hvY29sYXRlLiBCb25ueSBuZWVkcyB0byBwYXkgUGV0ZXIgMjkgcmFpc2lucyBmb3IgdGhpcy48XC9wPlxyXG5cclxuPHA+VGhlbiBCb25ueSBnaXZlcyBQZXRlciB0aGUgc21hbGxlciBvZiB0aGUgdHdvIGJsb2NrczogdGhlIG9uZSB0aGF0IGhhcyB0d28gcGllY2VzIHdpdGggNSByYWlzaW5zIGVhY2gsIGFuZCBhc2tzIFBldGVyIHRvIGN1dCB0aGUgYmxvY2sgaW4gdHdvIGluIGV4Y2hhbmdlIGZvciAxMCByYWlzaW5zLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGlzLCBCb25ueSBnaXZlcyBQZXRlciB0aGUgbGFyZ2VzdCByZW1haW5pbmcgYmxvY2s6IHRoZSBvbmUgaGF2aW5nIHBpZWNlcyB3aXRoIDIsIDcsIDEgYW5kIDkgcmFpc2lucyByZXNwZWN0aXZlbHkuIEJvbm55IGFza3MgUGV0ZXIgdG8gY3V0IGl0IGhvcml6b250YWxseSwgc2VwYXJhdGluZyB0aGUgZmlyc3QgYW5kIHRoZSBzZWNvbmQgcm93IGFuZCBwYXlzIGhpbSAxOSByYWlzaW5zLjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhpcywgQm9ubnkgZ2l2ZXMgUGV0ZXIgdGhlIHRvcC1sZWZ0IGJsb2NrLCBwYXlpbmcgOSByYWlzaW5zLiBGaW5hbGx5LCBCb25ueSBhc2tzIFBldGVyIHRvIHNwbGl0IHRoZSBib3R0b20tbGVmdCBibG9jaywgcGF5aW5nIDEwIHJhaXNpbnMuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCBjb3N0IHRvIEJvbm55IGlzIDI5ICsgMTAgKyAxOSArIDkgKyAxMCA9IDc3IHJhaXNpbnMuIE5vIG90aGVyIGN1dHRpbmcgYXJyYW5nZW1lbnQgY2FuIGdldCB0aGUgY2hvY29sYXRlIGN1dCBpbnRvIGl0cyA2IHBpZWNlcyBhdCBhIHNtYWxsZXIgY29zdC4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2009 4번

  • 문제를 번역한 사람: koosaga