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

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

예제 입력 1

2 6
7
10

예제 출력 1

28

예제 입력 2

7 10
3
8
3
6
9
2
4

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjMwNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3ODVcdWFkNmRcdWMyZWNcdWMwYWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVjNjI0XHVjMmE0XHVkMmI4XHViODA4XHVjNzdjXHViOWFjXHVjNTQ0XHViODVjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI1YTBcdWIwYWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVjZDFkIE1cdWJhODVcdWM3NzRcdWFjZTAsIFx1YzljMFx1YWUwOCBcdWFjZjVcdWQ1NmRcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMWNcdWMxMWMgXHVjNzg1XHVhZDZkXHVjMmVjXHVjMGFjXHViOTdjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YWQ2ZFx1YzJlY1x1YzBhY1x1YjMwMFx1YjI5NCBcdWNkMWQgTlx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM3ODVcdWFkNmRcdWMyZWNcdWMwYWNcdWFkMDBcdWM3NzQgXHVjMmVjXHVjMGFjXHViOTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjljOFx1YjJlNCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LiBrXHViYzg4IFx1YzJlY1x1YzBhY1x1YjMwMFx1YzVkMCBcdWM1NDlcdWM1NDRcdWM3ODhcdWIyOTQgXHVjMmVjXHVjMGFjXHVhZDAwXHVjNzc0IFx1ZDU1YyBcdWJhODVcdWM3NDQgXHVjMmVjXHVjMGFjXHViOTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFQ8c3ViPms8XC9zdWI+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWMyZWNcdWMwYWNcdWIzMDBcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVhY2UwLCBcdWMyZWNcdWMwYWNcdWI5N2MgXHVkNTYwIFx1YzkwMFx1YmU0NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMDVkXHViMGM4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YmU0NFx1ZDU4OVx1YWUzMCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjODA0XHVjMTM4XHViMGI0XHVhY2UwIFx1YjE4MFx1YjdlY1x1YWMxNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzljMFx1YWUwOCBcdWMyZWNcdWMwYWNcdWI5N2MgXHVhZTMwXHViMmU0XHViOWFjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViYWE4XHViNDUwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWMyZWNcdWMwYWNcdWIzMDBcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ1NWMgXHVjMGFjXHViNzhjXHViOWNjIFx1YzJlY1x1YzBhY1x1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzVkMCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMmVjXHVjMGFjXHViMzAwXHVhYzAwIFx1YmNmNFx1Yzc3NFx1YmE3NCBcdWFjNzBcdWFlMzBcdWI4NWMgXHVhYzAwXHVjMTFjIFx1YzJlY1x1YzBhY1x1Yjk3YyBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDU2ZFx1YzBjMSBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWIzNTQgXHViZTYwXHViOTc4IFx1YzJlY1x1YzBhY1x1YjMwMFx1Yzc1OCBcdWMyZWNcdWMwYWNcdWFjMDAgXHViMDVkXHViMDk4XHVhZTM4IFx1YWUzMFx1YjJlNFx1YjliMCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhZGY4IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWFjMDBcdWMxMWMgXHVjMmVjXHVjMGFjXHViOTdjIFx1YmMxYlx1YzU0NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWFjZjVcdWQ1NTlcdWFjZmMgXHVkNTU5XHVjMGRkXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzJlY1x1YzBhY1x1Yjk3YyBcdWJjMWJcdWM3M2NcdWJhNzQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMyZWNcdWMwYWNcdWI5N2MgXHViYzFiXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQyMFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjQ1MCBcdWMyZWNcdWMwYWNcdWIzMDBcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWMyZWNcdWMwYWNcdWI5N2MgXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzAxXHVhYzAxIDdcdWNkMDhcdWM2NDAgMTBcdWNkMDhcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM5MDRcdWM1ZDAgXHVjMTFjIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgNlx1YmE4NVx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHVhYzAwXHVjN2E1IFx1Y2NhYiBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Yzk4OVx1YzJkYyBcdWMyZWNcdWMwYWNcdWI5N2MgXHViYzFiXHVjNzNjXHViN2VjIFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuIDdcdWNkMDhcdWFjMDAgXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyZWNcdWMwYWNcdWIzMDBcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhZGY4XHVhY2YzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzExYyBcdWMyZWNcdWMwYWNcdWI5N2MgXHViYzFiXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC4gMTBcdWNkMDhcdWFjMDAgXHViNDE4XHViMjk0IFx1YzIxY1x1YWMwNCwgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzc0XHVhY2YzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzExYyBcdWMyZWNcdWMwYWNcdWI5N2MgXHViYzFiXHVjNzNjXHViYTc0IFx1YjQxOFx1YWNlMCwgMTRcdWNkMDhcdWFjMDAgXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWIyZTRcdWMxMmYgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzJlY1x1YzBhY1x1YjMwMFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NzRcdWMxMWMgXHVjMmVjXHVjMGFjXHViOTdjIFx1YmMxYlx1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuIDIwXHVjZDA4XHVhYzAwIFx1YjQxOFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMmVjXHVjMGFjXHViMzAwXHVhYzAwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNWVjXHVjMTJmIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhZGY4IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwLCAxXHVjZDA4XHViOTdjIFx1YjM1NCBcdWFlMzBcdWIyZTRcdWI5YjAgXHViMmU0XHVjNzRjXHVjNWQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMmVjXHVjMGFjXHViMzAwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzExYyBcdWMyZWNcdWMwYWNcdWI5N2MgXHViYzFiXHVjNzNjXHViYTc0LCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzJlY1x1YzBhY1x1Yjk3YyBcdWJjMWJcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCAyOFx1Y2QwOFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzBhY1x1Yjc4Y1x1Yzc3NCAxXHVjZDA4XHViOTdjIFx1YjM1NCBcdWFlMzBcdWIyZTRcdWI5YWNcdWM5YzBcdWM1NGFcdWFjZTAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMmVjXHVjMGFjXHViMzAwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMmVjXHVjMGFjXHViOTdjIFx1YmMxYlx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IDMwXHVjZDA4XHVhYzAwIFx1YjQxOFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjMmVjXHVjMGFjXHViOTdjIFx1YmMxYlx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IE0gJmxlOyAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzJlY1x1YzBhY1x1YjMwMFx1YzVkMFx1YzExYyBcdWMyZWNcdWMwYWNcdWI5N2MgXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzggVDxzdWI+azxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFQ8c3ViPms8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc3NCBcdWMyZWNcdWMwYWNcdWI5N2MgXHViOWM4XHVjZTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFFUk9EUk9NIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgQ3JvYXRpYW4gZGVsZWdhdGlvbiwgY29uc2lzdGluZyBvZiBNIHBlb3BsZSwgaXMgdHJhdmVsbGluZyB0byBJT0kgMjAxMyBpbiBBdXN0cmFsaWEuIFRoZXkgYXJlIGN1cnJlbnRseSB3YWl0aW5nIGluIGEgcXVldWUgZm9yIGNoZWNrLWluIGF0IHRoZSBhaXJwb3J0LiBUaGVyZSBhcmUgTiBjaGVjay1pbiBkZXNrcyBvcGVuLiBTb21lIG9mZmljaWFscyB3b3JrIG1vcmUgZWZmaWNpZW50bHkgdGhhbiBvdGhlcnMsIHNvIHRoZSBkZXNrcyBvcGVyYXRlIGF0IGRpZmZlcmVudCBzcGVlZHMuIEF0IHRoZSBrLXRoIGRlc2ssIFQ8c3ViPms8XC9zdWI+IHNlY29uZHMgYXJlIHJlcXVpcmVkIHRvIGZpbmlzaCBjaGVjay1pbiBvZiBhIHNpbmdsZSBwYXNzZW5nZXIsIGFuZCBtZW1iZXJzIG9mIG91ciBkZWxlZ2F0aW9uIGhhcHBlbiB0byBrbm93IHRoZSBleGFjdCBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgYmVnaW5uaW5nLCBhbGwgZGVza3MgYXJlIHJlYWR5IHRvIGFjY2VwdCB0aGUgbmV4dCBwYXNzZW5nZXIsIGFuZCB0aGUgZGVsZWdhdGlvbiBtZW1iZXJzIGFyZSB0aGUgb25seSBwZW9wbGUgaW4gdGhlIHF1ZXVlLiBBIHBlcnNvbiBjYW4gb25seSBvY2N1cHkgKHN0YXJ0IGNoZWNrLWluIGF0KSBhbiBhdmFpbGFibGUgZGVzayB3aGVuIGFsbCBwZW9wbGUgaW4gZnJvbnQgb2YgdGhhdCBwZXJzb24gaW4gdGhlIHF1ZXVlIGhhdmUgbGVmdCB0aGUgcXVldWUgKHN0YXJ0ZWQsIG5vdCBuZWNlc3NhcmlseSBmaW5pc2hlZCwgY2hlY2staW4pIGFscmVhZHkuIEF0IHRoYXQgbW9tZW50LCB0aGUgcGVyc29uIGNhbiBpbW1lZGlhdGVseSBvY2N1cHkgYW4gYXZhaWxhYmxlIGRlc2sgKGlmIHRoZXJlIGlzIG9uZSksIGJ1dCBjYW4gYWxzbyBjaG9vc2UgdG8gd2FpdCBmb3IgYW5vdGhlciAoZmFzdGVyKSBkZXNrIHRvIGJlY29tZSBhdmFpbGFibGUuIE91ciBkZWxlZ2F0aW9uIG1lbWJlcnMsIGJlaW5nIGNvbXB1dGVyIHNjaWVuY2UgZ2Vla3MsIG1ha2UgdGhpcyBkZWNpc2lvbiBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIG1vbWVudCB3aGVuIGFsbCBvZiB0aGVtIGhhdmUgZmluaXNoZWQgY2hlY2staW4gaXMgYXMgc29vbiBhcyBwb3NzaWJsZS4gWW91ciB0YXNrIGlzIGZpbmRpbmcgdGhhdCBtb21lbnQgaW4gdGltZS48XC9wPlxyXG5cclxuPHA+TGV0IHVzIGRlc2NyaWJlIHRoZSBzY2VuYXJpbyBmcm9tIHRoZSBmaXJzdCBleGFtcGxlIGJlbG93LiBUaGVyZSBhcmUgdHdvIGRlc2tzLCB3aXRoIHByb2Nlc3NpbmcgdGltZXMgb2YgNyBhbmQgMTAgc2Vjb25kcywgcmVzcGVjdGl2ZWx5LiBPdXQgb2YgdGhlIHNpeCBwZW9wbGUgaW4gdGhlIGRlbGVnYXRpb24sIHRoZSBmaXJzdCB0d28gaW1tZWRpYXRlbHkgb2NjdXB5IHRoZSB0d28gZGVza3MuIEF0IHRpbWUgNywgdGhlIGZpcnN0IGRlc2sgaXMgZnJlZWQsIGFuZCB0aGUgdGhpcmQgcGVyc29uIG9jY3VwaWVzIGl0LiBBdCB0aW1lIDEwLCB0aGUgZm91cnRoIHBlcnNvbiBvY2N1cGllcyB0aGUgc2Vjb25kIGRlc2suIEF0IHRpbWUgMTQsIHRoZSBmaWZ0aCBwZXJzb24gb2NjdXBpZXMgdGhlIGZpcnN0IGRlc2suIEF0IHRpbWUgMjAsIHRoZSBzZWNvbmQgZGVzayBpcyBmcmVlZCBhZ2FpbiwgYnV0IHRoZSBzaXh0aCBwZXJzb24gZGVjaWRlcyB0byB3YWl0IGFub3RoZXIgc2Vjb25kICh0aW1lIDIxKSBmb3IgdGhlIGZpcnN0IGRlc2sgdG8gYmVjb21lIGF2YWlsYWJsZSwgYW5kIHRoZW4gb2NjdXB5IGl0LiBUaGlzIHdheSwgdGhlIGNoZWNrLWluIGlzIGNvbXBsZXRlZCBieSB0aW1lIDI4LiBJZiB0aGUgc2l4dGggcGVyc29uIGhhZG4mIzM5O3Qgd2FpdGVkIGZvciB0aGUgZmFzdGVyIGRlc2ssIHRoZSBjaGVjay1pbiB3b3VsZCBoYXZlIHRha2VuIGEgdG90YWwgb2YgMzAgc2Vjb25kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBkZXNrcywgYW5kIE0gKDEgJmxlOyBNICZsZTsgMSAwMDAgMDAwIDAwMCksIHRoZSBudW1iZXIgb2YgcGVvcGxlIGluIHRoZSBkZWxlZ2F0aW9uLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIG51bWJlciBUayBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudCAoMSAmbGU7IFRrICZsZTsgMTA8c3VwPjk8XC9zdXA+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBtaW5pbXVtIHRpbWUgaW4gc2Vjb25kcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #3 4번