시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB312573520.588%

문제

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가 주어진다.

출력

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

제한

  • 1 ≤ N ≤ 1015
  • 1 ≤ P, V ≤ 1 000

예제 입력 1

9 1 1

예제 출력 1

8

예제 입력 2

6 1 2

예제 출력 2

8

예제 입력 3

6 2 1

예제 출력 3

12

힌트

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

W3sicHJvYmxlbV9pZCI6IjI0MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIyMDEyIFx1YzljMFx1YWQ2YyBcdWJhNzhcdWI5ZGQiLCJkZXNjcmlwdGlvbiI6IjxwPjIwMTJcdWIxNDQgXHVjOWMwXHVhZDZjXHViMjk0IFx1YmE3OFx1YjlkZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YmE3OFx1YjlkZFx1ZDU1OFx1YjI5NCBcdWM5YzBcdWFkNmNcdWI5N2MgXHVjOWMwXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjZDA4XHVhYzE1XHViMzAwXHVhZDZkIFx1YzBhY1x1ZDMwY1x1YjlhYyBcdWM2ZDRcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVhZTM0XHVhZTA5IFx1Yzc1OFx1ZDY4Y1x1Yjk3YyBcdWMxOGNcdWM5ZDFcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWM3NThcdWQ2OGNcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc1OCBcdWM3NThcdWM2ZDBcdWM3NzQgXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NThcdWQ2OGNcdWM1ZDBcdWIyOTQgXHVkNjhjXHVjNzU4XHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjNzU4XHVhY2FjXHVjNzQ0IFx1YWNiMFx1Yjg2MFx1YzczY1x1Yjg1YyBcdWIwYjhcdWIyZTQuIFx1ZDY4Y1x1Yzc1OFx1YzVkMFx1YzExYywgXHVhY2IwXHViODYwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQsIFx1ZDY4Y1x1Yzc1OCBcdWNjMzhcdWMxMWRcdWM3OTBcdWI0ZTRcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzc1OFx1YWNhY1x1Yzc3NCBcdWM3ODhcdWFjZTAsIFBcdWJkODRcdWIzZDlcdWM1NDggXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWMxMjRcdWJhODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1Y2MzOFx1YzExZFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWJjMWNcdWQ0NWNcdWI5N2MgXHVkNTVjIFx1ZDZjNFx1YzVkMCwgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1Yzc0MCBcdWM3NThcdWFjYWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWQyMmNcdWQ0NWNcdWIyOTQgVlx1YmQ4NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUCA9IDFcdWM3NzRcdWFjZTAsIFYgPSAxXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCwgMTAwXHViYTg1XHVjNzU4IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWNjMzhcdWMxMWRcdWQ1NWMgXHVkNjhjXHVjNzU4XHViNzdjXHViYTc0IFx1Y2Q1Y1x1Yzg4NSBcdWFjYjBcdWI4NjBcdWM3NzQgXHViMDk4XHVjNjI0XHVhZTMwIFx1YWU0Y1x1YzljMCAxMDFcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWFlMDggXHVjOWMwXHVhZDZjXHVhYzAwIFx1YmE3OFx1YjlkZFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YzBhY1x1ZDMwY1x1YjlhYyBcdWM2ZDRcdWI0ZGMgXHVjNzU4XHVjNmQwXHViNGU0XHVjNzQwIFx1Yzc1OFx1YzY3OFx1Yjg1YyBcdWNjNDVcdWM3ODRcdWFjMTBcdWM3NzQgXHViMTE4XHVjY2QwXHVjMTFjLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNzU4XHVjMGFjIFx1YWNiMFx1YzgxNSBcdWM4MDhcdWNjMjhcdWI5N2MgXHViZTYwXHViOTc0XHVhYzhjIFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHVjNzU4XHVjNmQwXHViNGU0XHVjNzQ0IFx1YjA5OFx1YjIwNFx1YWNlMCwgXHViM2Q5XHVjMmRjXHVjNWQwIFx1ZDY4Y1x1Yzc1OFx1Yjk3YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFjMDEgXHVhZGY4XHViOGY5XHVjNzQwIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjYzM4XHVjMTFkXHVjNzkwXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1Yzc1OFx1YWNhY1x1Yzc0NCBcdWJmNTFcdWFjZTAsIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1Yzc0MCBcdWM3NThcdWFjYWNcdWM3NDQgXHViMGI0XHViMTkzXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YjA3Y1x1YjlhYyBcdWIyZTRcdWMyZGMgXHVkNjhjXHVjNzU4XHViOTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUD0xLCBWPTFcdWM3NzRcdWFjZTAsIDEwMFx1YmE4NVx1Yzc1OCBcdWM3NThcdWM2ZDBcdWM3NDQgNDAsIDYwXHViYTg1XHVjNzU4IFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPjYwXHViYTg1XHVjNzU4IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWQ2OGNcdWM3NThcdWIyOTQgNjFcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT40MFx1YmE4NVx1Yzc1OCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVkNjhjXHVjNzU4XHViMjk0IDQxXHViZDg0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YWNlMCwgNjBcdWJhODVcdWM3NTgmbmJzcDtcdWFkZjhcdWI4ZjlcdWM3NTggXHVkNjhjXHVjNzU4XHVhYzAwIFx1YjA1ZFx1YjBhMCBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1Yzc1OFx1YWNhY1x1Yzc0NCBcdWIwYjggXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Y2Q1Y1x1Yzg4NSBcdWQ2OGNcdWM3NThcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTU4XHVhY2UwLCBcdWJjMWNcdWQ0NWNcdWQ1NThcdWIyOTRcdWIzNzAgMlx1YmQ4NCwgXHVkMjJjXHVkNDVjXHVkNTU4XHViMjk0XHViMzcwIDFcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWNkMWQgNjErMisxID0gNjRcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI4ZjlcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhYzcwXHVhZTMwXHVjMTFjIFx1YjYxMFx1YjJlNFx1Yjk3OCBcdWMxOGNcdWFkZjhcdWI4ZjlcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI1NGNcdWI1NGNcdWI4NWMgXHVjNzU4XHVjMGFjIFx1YWNiMFx1YzgxNSBcdWMxOGRcdWIzYzRcdWI5N2MgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWQ1NThcdWFlMzBcdWIzYzQgXHVkNTVjXHViMmU0LiBcdWQyYjlcdWJjYzRcdWQ1NWMgXHVjNjA4XHVjNjc4IFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWQ2OGNcdWM3NThcdWM3NTggXHVjYzM4XHVjMTFkXHVjNzkwXHVhYzAwIDFcdWJhODVcdWM3NzggXHVhY2IwXHVjODE1XHVkNTU4XHViMjk0XHViMzcwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNWQwXHVhYzhjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3NThcdWFjYWNcdWM3NDQgXHViYzFjXHVkNDVjXHVkNTYwIFx1ZDU0NFx1YzY5NFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgUFx1YzY0MCBWXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDY4Y1x1Yzc1OFx1YzY0MCBcdWFkZjhcdWI4ZjlcdWM3NDQgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzU4XHVhY2FjIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWIwOThcdWM2MjRcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgUFx1YzY0MCBWXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc1OFx1ZDY4Y1x1YWMwMCBcdWNkNWNcdWM4ODUgXHVjNzU4XHVhY2FjXHVjNzQ0IFx1YjBiNFx1YjI5NCBcdWMyZGNcdWFjMDQgTVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCAzXHViYTg1XHVjNTI5IDNcdWFjMWNcdWM3NTggXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YmE3NCwgXHVhYzAxIFx1YWRmOFx1YjhmOVx1Yzc0MCBcdWQ2OGNcdWM3NThcdWFjMDAgNFx1YmQ4NFx1YzUyOSBcdWFjNzhcdWI5YWNcdWFjZTAsIFx1YjJlNFx1YzJkYyBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgM1x1YmE4NVx1Yzc3NCBcdWQ2OGNcdWM3NThcdWM1ZDAgXHVjYzM4XHVjMTFkXHVkNTc0XHVjMTFjIFx1ZDY4Y1x1Yzc1OFx1Yjk3YyBcdWQ1NThcdWJhNzQgNFx1YmQ4NFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWJiYzBcdWI4NWMsIDhcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMTA8c3VwPjE1PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUCwgViAmbGU7IDEgMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyNDI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWVldGluZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBTb2NpZXR5IGZvciBTYXZpbmcgdGhlIFdvcmxkIGhhcyBjYWxsZWQgdGhlaXIgTiBtZW1iZXJzIHRvIGFuIGVtZXJnZW5jeSBjb25ncmVzcyB0byBmaW5hbGx5IGFncmVlIG9uIGEgcGxhbiBmb3Igc2F2aW5nIHRoZSB3b3JsZC4gVG8gcmVhY2ggYSBjb21tb24gZGVjaXNpb24gaW4gYW55IG1lZXRpbmcgYXQgdGhlIGNvbmdyZXNzLCB0aGUgbWVldGluZyBwYXJ0aWNpcGFudHMgcHJvY2VlZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkVhY2ggb2YgdGhlbSBoYXMgYSBwcm9wb3NhbCBhbmQgdGFrZXMgUCBtaW51dGVzIHRvIHByZXNlbnQgaXQgdG8gdGhlIG90aGVycy48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgYWxsIHBhcnRpY2lwYW50cyBoYXZlIG1hZGUgdGhlaXIgcHJlc2VudGF0aW9ucywgdGhleSB2b3RlIGZvciB0aGUgYmVzdCBwcm9wb3NhbCwgd2hpY2ggdGFrZXMgViBtaW51dGVzLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBlYWNoIHByb3Bvc2FsIHRha2VzIG9uZSBtaW51dGUgKFAgPSAxKSBhbmQgdm90aW5nIGFsc28gdGFrZXMgb25lIG1pbnV0ZSAoViA9IDEpLCBhIG1lZXRpbmcgd2l0aCAxMDAgcGFydGljaXBhbnRzIHdvdWxkIHJlYWNoIGEgZGVjaXNpb24gaW4gMTAxIG1pbnV0ZXMuPFwvcD5cclxuXHJcbjxwPlRvIHNwZWVkIHVwIHRoZSBvdmVyYWxsIGRlY2lzaW9uLW1ha2luZyBwcm9jZXNzLCB0aGUgcGFydGljaXBhbnRzIG9mIHRoZSBjb25ncmVzcyBoYXZlIGRlY2lkZWQgdG8gc3BsaXQgaW50byBncm91cHMgYW5kIHdvcmsgaW4gcGFyYWxsZWwuIEVhY2ggZ3JvdXAgc2VsZWN0cyB0aGUgYmVzdCBwcm9wb3NhbCBhbW9uZyB0aGVtc2VsdmVzIHVzaW5nIHRoZSBwcm9jZWR1cmUgZGVzY3JpYmVkIGFib3ZlLiBUaGVuIHRoZSByZXByZXNlbnRhdGl2ZXMgb2YgdGhlIGdyb3VwcyBtZWV0IGFuZCBwaWNrIHRoZSBcdWZiMDFuYWwgcGxhbiBhbW9uZyB0aGUgcHJvcG9zYWxzIHZvdGVkIGJlc3QgaW4gZWFjaCBncm91cC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZSAxMDAgcGFydGljaXBhbnRzIHdvdWxkIHNwbGl0IGludG8gdHdvIGdyb3VwcyBvZiA0MCBhbmQgNjAsIHJlc3BlY3RpdmVseSwgdGhlIHByb2Nlc3MgY291bGQgd29yayBhcyBmb2xsb3dzIChhZ2FpbiwgUCA9IFYgPSAxKTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgbGFyZ2VyIGdyb3VwIHRha2VzIDYxIG1pbnV0ZXMgdG8gc2VsZWN0IHRoZWlyIGJlc3QgcHJvcG9zYWw7PFwvbGk+XHJcblx0PGxpPnRoZSBzbWFsbGVyIGdyb3VwIHRha2VzIDQxIG1pbnV0ZXMgdG8gZG8gdGhlIHNhbWUgYW5kIHRoZW4gaGFzIHRvIHdhaXQgZm9yIHRoZSBsYXJnZXIgZ3JvdXAgdG8gZmluaXNoOzxcL2xpPlxyXG5cdDxsaT50aGVuIHRoZSB0d28gcmVwcmVzZW50YXRpdmVzIG9mIHRoZSBncm91cHMgbWVldCBhbmQgc3BlbmQgMiBtaW51dGVzIHByZXNlbnRpbmcgdG8gZWFjaCBvdGhlciBhbmQgMSBtaW51dGUgdG8gdm90ZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdG90YWwgdGltZSBzcGVudCBpcyB0aHVzIDYxICsgMiArIDEgPSA2NCBtaW51dGVzLjxcL3A+XHJcblxyXG48cD5CdXQgdGhlIGdyb3VwcyBtaWdodCBmdXJ0aGVyIGRpdmlkZSB0aGVtc2VsdmVzIGludG8gc3ViZ3JvdXBzIGFuZCBzb21ldGltZXMgaXQgY291bGQgYmUgdXNlZnVsIHRvIHNwbGl0IGludG8gbW9yZSB0aGFuIHR3byBncm91cHMuIEFzIGEgc3BlY2lhbCBjYXNlLCBhIHN1Ymdyb3VwIG9mIDEgbWVtYmVyIGNhbiBkZWNpZGUgaW4gbm8gdGltZSwgYXMgdGhlcmUgaXMgbm8gbmVlZCB0byBwcmVzZW50IG9uZSZyc3F1bztzIG93biBwcm9wb3NhbCB0byBvbmVzZWxmLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gcHJlc2VudGF0aW9uIGFuZCB2b3RpbmcgdGltZXMgUCBhbmQgViwgY29tcHV0ZXMgdGhlIG1pbmltYWwgdGltZSBuZWVkZWQgZm9yIHRoZSBOIHBhcnRpY2lwYW50cyBvZiB0aGUgY29uZ3Jlc3MgdG8gcmVhY2ggYSBjb21tb24gZGVjaXNpb24sIGFzc3VtaW5nIHRoZXkgb3JnYW5pemUgdGhlaXIgbWVldGluZ3MgYW5kIGdyb3VwcyBvcHRpbWFsbHkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHRocmVlIGludGVnZXJzIE4sIFAsIGFuZCBWOiBOIGlzIHRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzIG9mIHRoZSBjb25ncmVzcywgUCBpcyB0aGUgcHJlc2VudGF0aW9uIHRpbWUgKGluIG1pbnV0ZXMpLCBhbmQgViBpcyB0aGUgdm90aW5nIHRpbWUgKGluIG1pbnV0ZXMpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGludGVnZXIgTSwgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG1pbnV0ZXMgbmVlZGVkIGZvciB0aGUgY29uZ3Jlc3MgdG8gcmVhY2ggYSBkZWNpc2lvbi48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUsIHRoZSBwYXJ0aWNpcGFudHMgY2FuIGJlIGRpdmlkZWQgaW50byAzIGdyb3VwcyBvZiAzIG1lbWJlcnMgZWFjaC4gVGhlbiBlYWNoIGdyb3VwIG5lZWRzIDQgbWludXRlcyBhbmQgdGhlIDMgcmVwcmVzZW50YXRpdmVzIG5lZWQgYW5vdGhlciA0IG1pbnV0ZXMgZm9yIHRoZWlyIGZpbmFsIG1lZXRpbmcuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMTA8c3VwPjE1PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUCwgViAmbGU7IDEgMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 5번