시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 55 11 6 37.500%

문제

2012년 지구는 멸망한다. 이러한 멸망하는 지구를 지키기 위해서, 초강대국 사파리 월드에는 긴급 의회를 소집했다. 이 의회에는 N명의 의원이 있다. 

의회에는 회의를 통해서 하나의 의견을 결론으로 낸다. 회의에서, 결론에 도달하기 위해서는, 회의 참석자들이 다음과 같은 과정을 지켜야 한다.

  1. 모든 사람은 의견이 있고, P분동안 다른 사람들에게 설명할 수 있다.
  2. 모든 참석자들이 발표를 한 후에, 가장 좋은 의견에 대해 투표를 한다. 이 투표는 V분 걸린다.

예를 들어, P=1이고, V=1이라고 하면, 100명의 참가자가 참석한 회의라면 최종 결론이 나오기 까지 101분이 걸린다.

지금 지구가 멸망하고 있는데, 사파리 월드 의원들은 의외로 책임감이 넘쳐서, 이러한 의사 결정 절차를 빠르게 하기로 했다. 그러기 위해서 몇 개의 그룹으로 의원들을 나누고, 동시에 회의를 진행하기로 했다. 각 그룹은 각 그룹의 참석자들 사이에서 가장 좋은 의견을 뽑고, 각 그룹에서 가장 좋은 의견을 내놓은 사람들끼리 다시 회의를 한다.

예를 들어, P=1, V=1이고, 100명의 의원을 40, 60명의 그룹으로 나누면 다음과 같은 과정을 거친다.

  1. 60명의 그룹의 회의는 61분이 걸린다.
  2. 40명의 그룹의 회의는 41분이 걸리고, 60명의 그룹의 회의가 끝날 때 까지 기다린다.
  3. 두 그룹의 가장 좋은 의견을 낸 사람들이 최종 회의에 참가하고, 발표하는데 2분, 투표하는데 1분이 걸린다.

따라서 총 61+2+1 = 64분이 걸린다.

그룹을 만들었을 때, 거기서 또다른 소그룹을 만드는 것은 때때로 의사 결정 속도를 엄청나게 빠르게 하기도 한다. 특별한 예외 경우로 회의의 참석자가 1명인 결정하는데 시간이 걸리지 않고, 다른 사람에게 자신의 의견을 발표할 필요도 없다.

N과 P와 V가 주어졌을 때, 회의와 그룹을 최적의 상태로 나누었을 때, 마지막 의견 하나가 나오는데 걸리는 시간을 출력하시오.

입력

첫째 줄에 N과 P와 V가 주어진다. 1<=N<=10^15, 1<=P,V<=1,000

출력

첫째 줄에 의회가 최종 의견을 내는 시간 M을 출력한다.

예제 입력 1

9 1 1

예제 출력 1

8

힌트

3명씩 3개의 그룹으로 나누면, 각 그룹은 회의가 4분씩 걸리고, 다시 마지막에 3명이 회의에 참석해서 회의를 하면 4분이 걸리므로, 8분이 걸린다.

W3sicHJvYmxlbV9pZCI6IjI0MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIyMDEyIFx1YzljMFx1YWQ2YyBcdWJhNzhcdWI5ZGQiLCJkZXNjcmlwdGlvbiI6IjxwPjIwMTJcdWIxNDQgXHVjOWMwXHVhZDZjXHViMjk0IFx1YmE3OFx1YjlkZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmE3OFx1YjlkZFx1ZDU1OFx1YjI5NCBcdWM5YzBcdWFkNmNcdWI5N2MgXHVjOWMwXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjZDA4XHVhYzE1XHViMzAwXHVhZDZkIFx1YzBhY1x1ZDMwY1x1YjlhYyBcdWM2ZDRcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVhZTM0XHVhZTA5IFx1Yzc1OFx1ZDY4Y1x1Yjk3YyBcdWMxOGNcdWM5ZDFcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWM3NThcdWQ2OGNcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc1OCBcdWM3NThcdWM2ZDBcdWM3NzQgXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NThcdWQ2OGNcdWM1ZDBcdWIyOTQgXHVkNjhjXHVjNzU4XHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjNzU4XHVhY2FjXHVjNzQ0IFx1YWNiMFx1Yjg2MFx1YzczY1x1Yjg1YyBcdWIwYjhcdWIyZTQuIFx1ZDY4Y1x1Yzc1OFx1YzVkMFx1YzExYywgXHVhY2IwXHViODYwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQsIFx1ZDY4Y1x1Yzc1OCBcdWNjMzhcdWMxMWRcdWM3OTBcdWI0ZTRcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzc1OFx1YWNhY1x1Yzc3NCBcdWM3ODhcdWFjZTAsIFBcdWJkODRcdWIzZDlcdWM1NDggXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWMxMjRcdWJhODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1Y2MzOFx1YzExZFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWJjMWNcdWQ0NWNcdWI5N2MgXHVkNTVjIFx1ZDZjNFx1YzVkMCwgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1Yzc0MCBcdWM3NThcdWFjYWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWQyMmNcdWQ0NWNcdWIyOTQgVlx1YmQ4NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUD0xXHVjNzc0XHVhY2UwLCBWPTFcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0LCAxMDBcdWJhODVcdWM3NTggXHVjYzM4XHVhYzAwXHVjNzkwXHVhYzAwIFx1Y2MzOFx1YzExZFx1ZDU1YyBcdWQ2OGNcdWM3NThcdWI3N2NcdWJhNzQgXHVjZDVjXHVjODg1IFx1YWNiMFx1Yjg2MFx1Yzc3NCBcdWIwOThcdWM2MjRcdWFlMzAgXHVhZTRjXHVjOWMwIDEwMVx1YmQ4NFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YWUwOCBcdWM5YzBcdWFkNmNcdWFjMDAgXHViYTc4XHViOWRkXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjMGFjXHVkMzBjXHViOWFjIFx1YzZkNFx1YjRkYyBcdWM3NThcdWM2ZDBcdWI0ZTRcdWM3NDAgXHVjNzU4XHVjNjc4XHViODVjIFx1Y2M0NVx1Yzc4NFx1YWMxMFx1Yzc3NCBcdWIxMThcdWNjZDBcdWMxMWMsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM3NThcdWMwYWMgXHVhY2IwXHVjODE1IFx1YzgwOFx1Y2MyOFx1Yjk3YyBcdWJlNjBcdWI5NzRcdWFjOGMgXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWM3NThcdWM2ZDBcdWI0ZTRcdWM3NDQgXHViMDk4XHViMjA0XHVhY2UwLCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVkNjhjXHVjNzU4XHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NDAgXHVhYzAxIFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWNjMzhcdWMxMWRcdWM3OTBcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHVjNzU4XHVhY2FjXHVjNzQ0IFx1YmY1MVx1YWNlMCwgXHVhYzAxIFx1YWRmOFx1YjhmOVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1Yzc1OFx1YWNhY1x1Yzc0NCBcdWIwYjRcdWIxOTNcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHViMDdjXHViOWFjIFx1YjJlNFx1YzJkYyBcdWQ2OGNcdWM3NThcdWI5N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBQPTEsIFY9MVx1Yzc3NFx1YWNlMCwgMTAwXHViYTg1XHVjNzU4IFx1Yzc1OFx1YzZkMFx1Yzc0NCA0MCwgNjBcdWJhODVcdWM3NTggXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNlNWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+NjBcdWJhODVcdWM3NTggXHVhZGY4XHViOGY5XHVjNzU4IFx1ZDY4Y1x1Yzc1OFx1YjI5NCA2MVx1YmQ4NFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjQwXHViYTg1XHVjNzU4IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWQ2OGNcdWM3NThcdWIyOTQgNDFcdWJkODRcdWM3NzQgXHVhYzc4XHViOWFjXHVhY2UwLCA2MFx1YmE4NVx1Yzc1OCZuYnNwO1x1YWRmOFx1YjhmOVx1Yzc1OCBcdWQ2OGNcdWM3NThcdWFjMDAgXHViMDVkXHViMGEwIFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVhZTMwXHViMmU0XHViOWIwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHVhZGY4XHViOGY5XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHVjNzU4XHVhY2FjXHVjNzQ0IFx1YjBiOCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjZDVjXHVjODg1IFx1ZDY4Y1x1Yzc1OFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWFjZTAsIFx1YmMxY1x1ZDQ1Y1x1ZDU1OFx1YjI5NFx1YjM3MCAyXHViZDg0LCBcdWQyMmNcdWQ0NWNcdWQ1NThcdWIyOTRcdWIzNzAgMVx1YmQ4NFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViNTMwXHViNzdjXHVjMTFjIFx1Y2QxZCA2MSsyKzEgPSA2NFx1YmQ4NFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjhmOVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWFjNzBcdWFlMzBcdWMxMWMgXHViNjEwXHViMmU0XHViOTc4IFx1YzE4Y1x1YWRmOFx1YjhmOVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjU0Y1x1YjU0Y1x1Yjg1YyBcdWM3NThcdWMwYWMgXHVhY2IwXHVjODE1IFx1YzE4ZFx1YjNjNFx1Yjk3YyBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHViZTYwXHViOTc0XHVhYzhjIFx1ZDU1OFx1YWUzMFx1YjNjNCBcdWQ1NWNcdWIyZTQuIFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWM2MDhcdWM2NzggXHVhY2JkXHVjNmIwXHViODVjIFx1ZDY4Y1x1Yzc1OFx1Yzc1OCBcdWNjMzhcdWMxMWRcdWM3OTBcdWFjMDAgMVx1YmE4NVx1Yzc3OCBcdWFjYjBcdWM4MTVcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YzljMCBcdWM1NGFcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc1OFx1YWNhY1x1Yzc0NCBcdWJjMWNcdWQ0NWNcdWQ1NjAgXHVkNTQ0XHVjNjk0XHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YWNmYyBQXHVjNjQwIFZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNjhjXHVjNzU4XHVjNjQwIFx1YWRmOFx1YjhmOVx1Yzc0NCBcdWNkNWNcdWM4MDFcdWM3NTggXHVjMGMxXHVkMGRjXHViODVjIFx1YjA5OFx1YjIwNFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1YjljOFx1YzljMFx1YjljOSBcdWM3NThcdWFjYWMgXHVkNTU4XHViMDk4XHVhYzAwIFx1YjA5OFx1YzYyNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBQXHVjNjQwIFZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxJmx0Oz1OJmx0Oz0xMF4xNSwgMSZsdDs9UCxWJmx0Oz0xLDAwMDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzU4XHVkNjhjXHVhYzAwIFx1Y2Q1Y1x1Yzg4NSBcdWM3NThcdWFjYWNcdWM3NDQgXHViMGI0XHViMjk0IFx1YzJkY1x1YWMwNCBNXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+M1x1YmE4NVx1YzUyOSAzXHVhYzFjXHVjNzU4IFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWJhNzQsIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NDAgXHVkNjhjXHVjNzU4XHVhYzAwIDRcdWJkODRcdWM1MjkgXHVhYzc4XHViOWFjXHVhY2UwLCBcdWIyZTRcdWMyZGMgXHViOWM4XHVjOWMwXHViOWM5XHVjNWQwIDNcdWJhODVcdWM3NzQgXHVkNjhjXHVjNzU4XHVjNWQwIFx1Y2MzOFx1YzExZFx1ZDU3NFx1YzExYyBcdWQ2OGNcdWM3NThcdWI5N2MgXHVkNTU4XHViYTc0IDRcdWJkODRcdWM3NzQgXHVhYzc4XHViOWFjXHViYmMwXHViODVjLCA4XHViZDg0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1lZXRpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgU29jaWV0eSBmb3IgU2F2aW5nIHRoZSBXb3JsZCBoYXMgY2FsbGVkIHRoZWlyIE4gbWVtYmVycyB0byBhbiBlbWVyZ2VuY3kgY29uZ3Jlc3MgdG8gZmluYWxseSBhZ3JlZSBvbiBhIHBsYW4gZm9yIHNhdmluZyB0aGUgd29ybGQuIFRvIHJlYWNoIGEgY29tbW9uIGRlY2lzaW9uIGluIGFueSBtZWV0aW5nIGF0IHRoZSBjb25ncmVzcywgdGhlIG1lZXRpbmcgcGFydGljaXBhbnRzIHByb2NlZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FYWNoIG9mIHRoZW0gaGFzIGEgcHJvcG9zYWwgYW5kIHRha2VzIFAgbWludXRlcyB0byBwcmVzZW50IGl0IHRvIHRoZSBvdGhlcnMuPFwvbGk+XHJcblx0PGxpPkFmdGVyIGFsbCBwYXJ0aWNpcGFudHMgaGF2ZSBtYWRlIHRoZWlyIHByZXNlbnRhdGlvbnMsIHRoZXkgdm90ZSBmb3IgdGhlIGJlc3QgcHJvcG9zYWwsIHdoaWNoIHRha2VzIFYgbWludXRlcy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgZWFjaCBwcm9wb3NhbCB0YWtlcyBvbmUgbWludXRlIChQID0gMSkgYW5kIHZvdGluZyBhbHNvIHRha2VzIG9uZSBtaW51dGUgKFYgPSAxKSwgYSBtZWV0aW5nIHdpdGggMTAwIHBhcnRpY2lwYW50cyB3b3VsZCByZWFjaCBhIGRlY2lzaW9uIGluIDEwMSBtaW51dGVzLjxcL3A+XHJcblxyXG48cD5UbyBzcGVlZCB1cCB0aGUgb3ZlcmFsbCBkZWNpc2lvbi1tYWtpbmcgcHJvY2VzcywgdGhlIHBhcnRpY2lwYW50cyBvZiB0aGUgY29uZ3Jlc3MgaGF2ZSBkZWNpZGVkIHRvIHNwbGl0IGludG8gZ3JvdXBzIGFuZCB3b3JrIGluIHBhcmFsbGVsLiBFYWNoIGdyb3VwIHNlbGVjdHMgdGhlIGJlc3QgcHJvcG9zYWwgYW1vbmcgdGhlbXNlbHZlcyB1c2luZyB0aGUgcHJvY2VkdXJlIGRlc2NyaWJlZCBhYm92ZS4gVGhlbiB0aGUgcmVwcmVzZW50YXRpdmVzIG9mIHRoZSBncm91cHMgbWVldCBhbmQgcGljayB0aGUgXHVmYjAxbmFsIHBsYW4gYW1vbmcgdGhlIHByb3Bvc2FscyB2b3RlZCBiZXN0IGluIGVhY2ggZ3JvdXAuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgMTAwIHBhcnRpY2lwYW50cyB3b3VsZCBzcGxpdCBpbnRvIHR3byBncm91cHMgb2YgNDAgYW5kIDYwLCByZXNwZWN0aXZlbHksIHRoZSBwcm9jZXNzIGNvdWxkIHdvcmsgYXMgZm9sbG93cyAoYWdhaW4sIFAgPSBWID0gMSk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGxhcmdlciBncm91cCB0YWtlcyA2MSBtaW51dGVzIHRvIHNlbGVjdCB0aGVpciBiZXN0IHByb3Bvc2FsOzxcL2xpPlxyXG5cdDxsaT50aGUgc21hbGxlciBncm91cCB0YWtlcyA0MSBtaW51dGVzIHRvIGRvIHRoZSBzYW1lIGFuZCB0aGVuIGhhcyB0byB3YWl0IGZvciB0aGUgbGFyZ2VyIGdyb3VwIHRvIGZpbmlzaDs8XC9saT5cclxuXHQ8bGk+dGhlbiB0aGUgdHdvIHJlcHJlc2VudGF0aXZlcyBvZiB0aGUgZ3JvdXBzIG1lZXQgYW5kIHNwZW5kIDIgbWludXRlcyBwcmVzZW50aW5nIHRvIGVhY2ggb3RoZXIgYW5kIDEgbWludXRlIHRvIHZvdGUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHRvdGFsIHRpbWUgc3BlbnQgaXMgdGh1cyA2MSArIDIgKyAxID0gNjQgbWludXRlcy48XC9wPlxyXG5cclxuPHA+QnV0IHRoZSBncm91cHMgbWlnaHQgZnVydGhlciBkaXZpZGUgdGhlbXNlbHZlcyBpbnRvIHN1Ymdyb3VwcyBhbmQgc29tZXRpbWVzIGl0IGNvdWxkIGJlIHVzZWZ1bCB0byBzcGxpdCBpbnRvIG1vcmUgdGhhbiB0d28gZ3JvdXBzLiBBcyBhIHNwZWNpYWwgY2FzZSwgYSBzdWJncm91cCBvZiAxIG1lbWJlciBjYW4gZGVjaWRlIGluIG5vIHRpbWUsIGFzIHRoZXJlIGlzIG5vIG5lZWQgdG8gcHJlc2VudCBvbmUmcnNxdW87cyBvd24gcHJvcG9zYWwgdG8gb25lc2VsZi48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHByZXNlbnRhdGlvbiBhbmQgdm90aW5nIHRpbWVzIFAgYW5kIFYgLCBjb21wdXRlcyB0aGUgbWluaW1hbCB0aW1lIG5lZWRlZCBmb3IgdGhlIE4gcGFydGljaXBhbnRzIG9mIHRoZSBjb25ncmVzcyB0byByZWFjaCBhIGNvbW1vbiBkZWNpc2lvbiwgYXNzdW1pbmcgdGhleSBvcmdhbml6ZSB0aGVpciBtZWV0aW5ncyBhbmQgZ3JvdXBzIG9wdGltYWxseS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgdGhyZWUgaW50ZWdlcnMgTiwgUCwgYW5kIFYgOiBOIGlzIHRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzIG9mIHRoZSBjb25ncmVzcywgUCBpcyB0aGUgcHJlc2VudGF0aW9uIHRpbWUgKGluIG1pbnV0ZXMpLCBhbmQgViBpcyB0aGUgdm90aW5nIHRpbWUgKGluIG1pbnV0ZXMpLiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCAxICZsZTsgUCxWICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBpbnRlZ2VyIE0sIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtaW51dGVzIG5lZWRlZCBmb3IgdGhlIGNvbmdyZXNzIHRvIHJlYWNoIGEgZGVjaXNpb24uPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBwYXJ0aWNpcGFudHMgY2FuIGJlIGRpdmlkZWQgaW50byAzIGdyb3VwcyBvZiAzIG1lbWJlcnMgZWFjaC4gVGhlbiBlYWNoIGdyb3VwIG5lZWRzIDQgbWludXRlcyBhbmQgdGhlIDMgcmVwcmVzZW50YXRpdmVzIG5lZWQgYW5vdGhlciA0IG1pbnV0ZXMgZm9yIHRoZWlyIFx1ZmIwMW5hbCBtZWV0aW5nLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 5번