시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 98 62 41 70.690%

문제

플로브디브의 유명한 초콜릿 가공업자 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+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM3NFx1ZDNlY1x1YjNjNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTixNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVkNmM0IE5cdWFjMWMgXHVjOTA0XHVjNWQwIE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFJpalx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBpXHVkNTg5IGpcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM3NFx1ZDNlY1x1YjNjNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gTixNICZsdDs9IDUwPFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gUmksaiAmbHQ7PSAxMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Cb25ueVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3NFx1ZDNlY1x1YjNjNFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3OTBcdWI5NzRcdWJhNzQgNzdcdWFjMWNcdWM3NTggXHVhYzc0XHVkM2VjXHViM2M0XHViOTdjIFx1YzhmY1x1YWNlMCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDQgXHVjNzkwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9yYWlzaW5zMi5wbmdcIiBzdHlsZT1cImhlaWdodDo4MnB4OyB3aWR0aDo3MTFweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQ2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJhaXNpbnMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3JhaXNpbnMucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE3MXB4OyB3aWR0aDoyNTJweFwiIFwvPlBsb3ZkaXYmcnNxdW87cyBmYW1vdXMgbWFzdGVyIGNob2NvbGF0aWVyIEJvbm55IG5lZWRzIHRvIGN1dCBhIHNsYWIgb2YgY2hvY29sYXRlIHdpdGggcmFpc2lucy4gVGhlIGNob2NvbGF0ZSBpcyBhIHJlY3Rhbmd1bGFyIGJsb2NrIG9mIGlkZW50aWNhbCBzcXVhcmUgcGllY2VzLiBUaGUgcGllY2VzIGFyZSBhbGlnbmVkIHdpdGggdGhlIGVkZ2VzIG9mIHRoZSBjaG9jb2xhdGUsIGFuZCB0aGV5IGFyZSBhcnJhbmdlZCBpbiBOIHJvd3MgYW5kIE0gY29sdW1ucywgZm9yIGEgdG90YWwgb2YgTipNIHBpZWNlcy4gRWFjaCBwaWVjZSBoYXMgb25lIG9yIG1vcmUgcmFpc2lucyBvbiBpdCwgYW5kIG5vIHJhaXNpbnMgbGllIGJldHdlZW4gb3IgYWNyb3NzIHBpZWNlcy48XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5LCB0aGUgY2hvY29sYXRlIGlzIG9uZSBzaW5nbGUsIG1vbm9saXRoaWMgYmxvY2suIEJvbm55IG5lZWRzIHRvIGN1dCBpdCBpbnRvIHNtYWxsZXIgYW5kIHNtYWxsZXIgYmxvY2tzIHVudGlsIGZpbmFsbHkgc2hlIGhhcyBjdXQgdGhlIGNob2NvbGF0ZSBkb3duIHRvIGl0cyBOKk0gaW5kaXZpZHVhbCBwaWVjZXMuIEFzIEJvbm55IGlzIHZlcnkgYnVzeSwgc2hlIG5lZWRzIHRoZSBoZWxwIG9mIGhlciBhc3Npc3RhbnQsIFNseSBQZXRlciwgdG8gZG8gdGhlIGN1dHRpbmcuIFBldGVyIG9ubHkgbWFrZXMgc3RyYWlnaHQgbGluZSwgZW5kLXRvLWVuZCBjdXRzIGFuZCBoZSB3YW50cyB0byBiZSBwYWlkIGZvciBldmVyeSBzaW5nbGUgY3V0IGhlIG1ha2VzLiBCb25ueSBoYXMgbm8gbW9uZXkgYXQgaGFuZCwgYnV0IHNoZSBoYXMgcGxlbnR5IG9mIHJhaXNpbnMgbGVmdCBvdmVyLCBzbyBzaGUgb2ZmZXJzIHRvIHBheSBQZXRlciBpbiByYWlzaW5zLiBTbHkgUGV0ZXIgYWdyZWVzIHRvIHRoaXMgYXJyYW5nZW1lbnQsIGJ1dCB1bmRlciB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbjogZXZlcnkgdGltZSBoZSBjdXRzIGEgZ2l2ZW4gYmxvY2sgb2YgY2hvY29sYXRlIGludG8gdHdvIHNtYWxsZXIgYmxvY2tzLCBoZSBoYXMgdG8gYmUgcGFpZCBhcyBtYW55IHJhaXNpbnMgYXMgdGhlcmUgYXJlIG9uIHRoZSBibG9jayBoZSB3YXMgZ2l2ZW4uPFwvcD5cclxuXHJcbjxwPkJvbm55IHdhbnRzIHRvIHBheSBQZXRlciBhcyBsaXR0bGUgYXMgcG9zc2libGUuIFNoZSBrbm93cyBob3cgbWFueSByYWlzaW5zIHRoZXJlIGFyZSBvbiBlYWNoIG9mIHRoZSBOKk0gcGllY2VzLiBTaGUgY2FuIGNob29zZSB0aGUgb3JkZXIgaW4gd2hpY2ggc2hlIGdpdmVzIFBldGVyIGFueSByZW1haW5pbmcgYmxvY2tzLCBhbmQgc2hlIGNhbiBhbHNvIHRlbGwgUGV0ZXIgd2hhdCBjdXRzIHRvIG1ha2UgKGhvcml6b250YWwgb3IgdmVydGljYWwpIGFuZCB3aGVyZSBleGFjdGx5IHRvIG1ha2UgdGhlbS4gSGVscCBCb25ueSBkZWNpZGUgaG93IHRvIGN1dCB0aGUgY2hvY29sYXRlIGludG8gaW5kaXZpZHVhbCBwaWVjZXMsIHNvIHRoYXQgc2hlIHBheXMgU2x5IFBldGVyIGFzIGZldyByYWlzaW5zIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIG51bWJlciBvZiByYWlzaW5zIG9uIGVhY2ggb2YgdGhlIGluZGl2aWR1YWwgcGllY2VzLCBkZXRlcm1pbmVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiByYWlzaW5zIHRoYXQgQm9ubnkgd2lsbCBoYXZlIHRvIHBheSBTbHkgUGV0ZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gbXVzdCByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQgdGhlIGZvbGxvd2luZyBkYXRhOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOIGFuZCBNLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IE4gbGluZXMgZGVzY3JpYmUgaG93IG1hbnkgcmFpc2lucyB0aGVyZSBhcmUgb24gZWFjaCBwaWVjZSBvZiB0aGUgY2hvY29sYXRlLiBUaGUga3RoIG9mIHRoZXNlIE4gbGluZXMgZGVzY3JpYmVzIHRoZSBrdGggcm93IG9mIHRoZSBjaG9jb2xhdGUuIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIE0gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZSBpbnRlZ2VycyBkZXNjcmliZSB0aGUgcGllY2VzIG9uIHRoZSBjb3JyZXNwb25kaW5nIHJvdyBpbiBvcmRlciBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZSBwdGggaW50ZWdlciBvbiB0aGUga3RoIGxpbmUgKGFtb25nIHRoZXNlIE4gbGluZXMpIHRlbGxzIHlvdSBob3cgbWFueSByYWlzaW5zIGFyZSBvbiB0aGUgcGllY2UgaW4gdGhlIGt0aCByb3cgYW5kIHRoZSBwdGggY29sdW1uLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE4sIE0gJmxlOyA1MCBUaGUgbnVtYmVyIG9mIHBpZWNlcyBvbiBlYWNoIHNpZGUgb2YgdGhlIGNob2NvbGF0ZTxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUmsscCAmbGU7IDEwMDAgVGhlIG51bWJlciBvZiByYWlzaW5zIG9uIHRoZSBwaWVjZSBpbiB0aGUga3RoIHJvdyBhbmQgdGhlIHB0aCBjb2x1bW48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBtdXN0IHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIHJhaXNpbnMgdGhhdCBCb25ueSB3b3VsZCBoYXZlIHRvIHBheSBTbHkgUGV0ZXIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPk9uZSBwb3NzaWJsZSB3YXkgKG91dCBvZiBtYW55KSB0byBhY2hpZXZlIGEgY29zdCBvZiA3NyBpcyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9yYWlzaW5zMi5wbmdcIiBzdHlsZT1cImhlaWdodDo4MnB4OyB3aWR0aDo3MTFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgY3V0IHRoYXQgQm9ubnkgYXNrcyBQZXRlciB0byBtYWtlIHNlcGFyYXRlcyB0aGUgdGhpcmQgY29sdW1uIGZyb20gdGhlIHJlc3Qgb2YgdGhlIGNob2NvbGF0ZS4gQm9ubnkgbmVlZHMgdG8gcGF5IFBldGVyIDI5IHJhaXNpbnMgZm9yIHRoaXMuPFwvcD5cclxuXHJcbjxwPlRoZW4gQm9ubnkgZ2l2ZXMgUGV0ZXIgdGhlIHNtYWxsZXIgb2YgdGhlIHR3byBibG9ja3M6IHRoZSBvbmUgdGhhdCBoYXMgdHdvIHBpZWNlcyB3aXRoIDUgcmFpc2lucyBlYWNoLCBhbmQgYXNrcyBQZXRlciB0byBjdXQgdGhlIGJsb2NrIGluIHR3byBpbiBleGNoYW5nZSBmb3IgMTAgcmFpc2lucy48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhpcywgQm9ubnkgZ2l2ZXMgUGV0ZXIgdGhlIGxhcmdlc3QgcmVtYWluaW5nIGJsb2NrOiB0aGUgb25lIGhhdmluZyBwaWVjZXMgd2l0aCAyLCA3LCAxIGFuZCA5IHJhaXNpbnMgcmVzcGVjdGl2ZWx5LiBCb25ueSBhc2tzIFBldGVyIHRvIGN1dCBpdCBob3Jpem9udGFsbHksIHNlcGFyYXRpbmcgdGhlIGZpcnN0IGFuZCB0aGUgc2Vjb25kIHJvdyBhbmQgcGF5cyBoaW0gMTkgcmFpc2lucy48XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIHRoaXMsIEJvbm55IGdpdmVzIFBldGVyIHRoZSB0b3AtbGVmdCBibG9jaywgcGF5aW5nIDkgcmFpc2lucy4gRmluYWxseSwgQm9ubnkgYXNrcyBQZXRlciB0byBzcGxpdCB0aGUgYm90dG9tLWxlZnQgYmxvY2ssIHBheWluZyAxMCByYWlzaW5zLjxcL3A+XHJcblxyXG48cD5UaGUgdG90YWwgY29zdCB0byBCb25ueSBpcyAyOSArIDEwICsgMTkgKyA5ICsgMTAgPSA3NyByYWlzaW5zLiBObyBvdGhlciBjdXR0aW5nIGFycmFuZ2VtZW50IGNhbiBnZXQgdGhlIGNob2NvbGF0ZSBjdXQgaW50byBpdHMgNiBwaWVjZXMgYXQgYSBzbWFsbGVyIGNvc3QuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2009 4번

  • 문제를 번역한 사람: koosaga