시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB167433230.189%

문제

승재는 유명한 관광회사 ALPS(Amazing and Lovely and Perfect Sightseeing) 에서 버스기사로 일하고있다. 특히 승재가 태워주는 World Final 행 버스는 승차감이 최고인 것으로 유명하다.

승재가 하는 일은  ALPS 본사에서 버스를 타고 출발해 h개의 호텔에서 관광객들을 한 명씩 pick up 해서 관광지에 데려다 준 뒤, 그들을 다시 원래 호텔로 돌려보내고 ALPS 본사로 돌아오는 일이다. ALPS가 좋아하는 관광지는 ACM(Amazing Common Mountain) 뿐이기 때문에 관광지는 늘 ACM 한 곳만을 둘러보면 된다고 한다.

ALPS는 서비스정신이 뛰어난 회사이기 때문에, pick up을 먼저 한 관광객들부터 호텔로 돌려보내려고 노력한다. (먼저 pick up된 관광객이 남들보다 늦게 내린다면 그는 자신이 차별대우를 받고있다고 생각할 것이고, 항의가 들어온다면 ALPS는 망하게 된다.) 이에 ALPS는 자신만의 pick up 정책을 만들었다.

h개의 호텔에서 관광객들을 pick up 하는 경우, h/2번째 순서 이내로 pick up한 관광객들은 관광이 끝난 뒤 호텔로 돌려보내 줄 때도 h/2번째 순서 이내로 호텔로 돌려보내주어야 한다는 정책이다. 

(즉, 1 2 3 4 5 순서대로 pick up 했다면 돌아올 때 2 1 3 4 5 나 1 2 5 3 4 순으로 돌려보내주는 것은 가능하지만 1 3 2 4 5 순으로 돌려보내주면 안 된다. 2번째로 pick up 된 관광객이 5/2보다 큰 3번째로 내렸기 때문이다.)

승재는 버스의 기름값을 아끼고 싶기 때문에 하루동안 버스가 움직여야하는 경로의 길이를 최소로 하고 싶어졌다. ALPS 본사와 호텔들, 그리고 ACM 관광지 사이의 거리정보가 주어졌을 때, 정책을 만족하면서 버스가 움직여야하는 경로의 최솟값을 구하는 것이 이 문제이다.

정책에는 관광객을 태우고 내리는 순서만 정했기 때문에 이 정책을 지키면 최단경로가 안될 수도 있고, 어쩔때는 호텔을 그냥 지나쳐야하는 상황이 올 수도 있다. 하지만 ALPS는 그런 '사소한'것은 신경쓰지 않는다. 단지 저 정책을 지키면서 최단경로로 움직이는 데에만 집중하면 된다.

World Final 행 버스를 태운 경력이 있는 승재는 이미 답을 구하는 프로그램을 작성했다. 우리도 답을 구할 수 있음을 증명해보자.

입력

각 케이스마다 첫째 줄에는 정점의 수 n ( 3 ≤ n ≤ 20) 과 간선의 수 m (2 ≤ m ) 이 주어진다. (n은 호텔과 관광지, 그리고 출발지점을 모두 포함한 개수이다.)

정점은 0~n-1까지 번호가 메겨지는데, 0번 정점은 버스의 출발지점이고, n-1번 정점은 관광지, 나머지 1~n-2번 정점은 호텔을 의미한다. 

이어서 m개의 줄에 세 정수 u,v,t 가 주어진다. (0 ≤ u,v ≤ n-1, 1 ≤ t ≤ 3600) 이는 u u에서 v로 가는데 t만큼의 시간이 걸린다는 것을 의미한다. 길은 양방향이기 때문에 v에서 u로 가는데에도 t만큼의 시간이 걸린다.

임의의 한 정점으로 부터 다른 임의의 정점으로 가는 경로가 반드시 하나 이상 존재한다고 가정해도 좋다.

출력

각 케이스마다 "Case t: d" 를 출력한다. t는 케이스 번호이고, d는 조건을 만족하는 가장 짧은 경로의 이동거리이다.

예제 입력 1

5 4
0 1 10
1 2 20
2 3 30
3 4 40
4 6
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1

예제 출력 1

Case 1: 300
Case 2: 6
W3sicHJvYmxlbV9pZCI6IjQyMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjODRcdWMyYTRcdWFlMzBcdWMwYWMgXHVjMmI5XHVjN2FjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYjlcdWM3YWNcdWIyOTQgXHVjNzIwXHViYTg1XHVkNTVjIFx1YWQwMFx1YWQxMVx1ZDY4Y1x1YzBhYyBBTFBTKEFtYXppbmcgYW5kIExvdmVseSBhbmQgUGVyZmVjdCBTaWdodHNlZWluZykgXHVjNWQwXHVjMTFjIFx1YmM4NFx1YzJhNFx1YWUzMFx1YzBhY1x1Yjg1YyBcdWM3N2NcdWQ1NThcdWFjZTBcdWM3ODhcdWIyZTQuIFx1ZDJiOVx1ZDc4OCBcdWMyYjlcdWM3YWNcdWFjMDAgXHVkMGRjXHVjNmNjXHVjOGZjXHViMjk0IFdvcmxkIEZpbmFsIFx1ZDU4OSBcdWJjODRcdWMyYTRcdWIyOTQgXHVjMmI5XHVjYzI4XHVhYzEwXHVjNzc0IFx1Y2Q1Y1x1YWNlMFx1Yzc3OCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYjlcdWM3YWNcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCZuYnNwOyZuYnNwO0FMUFMgXHViY2Y4XHVjMGFjXHVjNWQwXHVjMTFjIFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWQwYzBcdWFjZTAmbmJzcDtcdWNkOWNcdWJjMWNcdWQ1NzQmbmJzcDtoXHVhYzFjXHVjNzU4IFx1ZDYzOFx1ZDE1NFx1YzVkMFx1YzExYyBcdWFkMDBcdWFkMTFcdWFjMWRcdWI0ZTRcdWM3NDQgXHVkNTVjIFx1YmE4NVx1YzUyOSBwaWNrIHVwIFx1ZDU3NFx1YzExYyBcdWFkMDBcdWFkMTFcdWM5YzBcdWM1ZDAgXHViMzcwXHViODI0XHViMmU0IFx1YzkwMCBcdWI0YTQsIFx1YWRmOFx1YjRlNFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVjNmQwXHViNzk4IFx1ZDYzOFx1ZDE1NFx1Yjg1YyBcdWIzY2NcdWI4MjRcdWJjZjRcdWIwYjRcdWFjZTAgQUxQUyBcdWJjZjhcdWMwYWNcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gQUxQU1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQmbmJzcDtcdWFkMDBcdWFkMTFcdWM5YzBcdWIyOTQmbmJzcDtBQ00oQW1hemluZyBDb21tb24gTW91bnRhaW4pIFx1YmZkMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhZDAwXHVhZDExXHVjOWMwXHViMjk0Jm5ic3A7XHViMjk4IEFDTSZuYnNwO1x1ZDU1YyBcdWFjZjNcdWI5Y2NcdWM3NDQgXHViNDU4XHViN2VjXHViY2Y0XHViYTc0IFx1YjQxY1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFMUFNcdWIyOTQgXHVjMTFjXHViZTQ0XHVjMmE0XHVjODE1XHVjMmUwXHVjNzc0IFx1YjZmMFx1YzViNFx1YjA5YyBcdWQ2OGNcdWMwYWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBwaWNrIHVwXHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWQ1NWMgXHVhZDAwXHVhZDExXHVhYzFkXHViNGU0XHViZDgwXHVkMTMwIFx1ZDYzOFx1ZDE1NFx1Yjg1YyBcdWIzY2NcdWI4MjRcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHViMTc4XHViODI1XHVkNTVjXHViMmU0LiAoXHViYTNjXHVjODAwIHBpY2sgdXBcdWI0MWMgXHVhZDAwXHVhZDExXHVhYzFkXHVjNzc0IFx1YjBhOFx1YjRlNFx1YmNmNFx1YjJlNCBcdWIyYTZcdWFjOGMgXHViMGI0XHViOWIwXHViMmU0XHViYTc0IFx1YWRmOFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjYzI4XHViY2M0XHViMzAwXHVjNmIwXHViOTdjIFx1YmMxYlx1YWNlMFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWQ1NmRcdWM3NThcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0XHViYTc0IEFMUFNcdWIyOTQgXHViOWRkXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4pIFx1Yzc3NFx1YzVkMCBBTFBTXHViMjk0IFx1Yzc5MFx1YzJlMFx1YjljY1x1Yzc1OCBwaWNrIHVwIFx1YzgxNVx1Y2M0NVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmhcdWFjMWNcdWM3NTggXHVkNjM4XHVkMTU0XHVjNWQwXHVjMTFjIFx1YWQwMFx1YWQxMVx1YWMxZFx1YjRlNFx1Yzc0NCBwaWNrIHVwIFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAsIGhcLzJcdWJjODhcdWM5ZjggXHVjMjFjXHVjMTFjJm5ic3A7XHVjNzc0XHViMGI0XHViODVjIHBpY2sgdXBcdWQ1NWMgXHVhZDAwXHVhZDExXHVhYzFkXHViNGU0XHVjNzQwIFx1YWQwMFx1YWQxMVx1Yzc3NCBcdWIwNWRcdWIwOWMgXHViNGE0IFx1ZDYzOFx1ZDE1NFx1Yjg1YyBcdWIzY2NcdWI4MjRcdWJjZjRcdWIwYjQgXHVjOTA0IFx1YjU0Y1x1YjNjNCBoXC8yXHViYzg4XHVjOWY4IFx1YzIxY1x1YzExYyBcdWM3NzRcdWIwYjRcdWI4NWMgXHVkNjM4XHVkMTU0XHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjODE1XHVjYzQ1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD4oXHVjOTg5LCAxIDIgMyA0IDUgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIHBpY2sgdXAgXHVkNTg4XHViMmU0XHViYTc0IFx1YjNjY1x1YzU0NFx1YzYyYyBcdWI1NGMgMiAxIDMgNCA1IFx1YjA5OCAxIDIgNSAzIDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YzhmY1x1YjI5NCBcdWFjODNcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTU4XHVjOWMwXHViOWNjIDEgMyAyIDQgNSBcdWMyMWNcdWM3M2NcdWI4NWMgXHViM2NjXHViODI0XHViY2Y0XHViMGI0XHVjOGZjXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIDJcdWJjODhcdWM5ZjhcdWI4NWMgcGljayB1cCBcdWI0MWMgXHVhZDAwXHVhZDExXHVhYzFkXHVjNzc0IDVcLzJcdWJjZjRcdWIyZTQgXHVkMDcwIDNcdWJjODhcdWM5ZjhcdWI4NWMgXHViMGI0XHViODM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzJiOVx1YzdhY1x1YjI5NCBcdWJjODRcdWMyYTRcdWM3NTggXHVhZTMwXHViOTg0XHVhYzEyXHVjNzQ0IFx1YzU0NFx1YjA3Y1x1YWNlMCBcdWMyZjZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwJm5ic3A7XHVkNTU4XHViOGU4XHViM2Q5XHVjNTQ4IFx1YmM4NFx1YzJhNFx1YWMwMCZuYnNwO1x1YzZjMFx1YzljMVx1YzVlY1x1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjJm5ic3A7XHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjRcdWM4NGNcdWIyZTQuIEFMUFMgXHViY2Y4XHVjMGFjXHVjNjQwIFx1ZDYzOFx1ZDE1NFx1YjRlNCwgXHVhZGY4XHViOWFjXHVhY2UwIEFDTSBcdWFkMDBcdWFkMTFcdWM5YzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4MTVcdWNjNDVcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIFx1YmM4NFx1YzJhNFx1YWMwMCBcdWM2YzBcdWM5YzFcdWM1ZWNcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1Y2M0NVx1YzVkMFx1YjI5NCBcdWFkMDBcdWFkMTFcdWFjMWRcdWM3NDQgXHVkMGRjXHVjNmIwXHVhY2UwIFx1YjBiNFx1YjlhY1x1YjI5NCBcdWMyMWNcdWMxMWNcdWI5Y2MgXHVjODE1XHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3NzQgXHVjODE1XHVjYzQ1XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NCBcdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNTQ4XHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YzViNFx1Y2E1NFx1YjU0Y1x1YjI5NCBcdWQ2MzhcdWQxNTRcdWM3NDQgXHVhZGY4XHViMGU1IFx1YzljMFx1YjA5OFx1Y2NkMFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NzQgXHVjNjJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBBTFBTXHViMjk0IFx1YWRmOFx1YjdmMCAmIzM5O1x1YzBhY1x1YzE4Y1x1ZDU1YyYjMzk7XHVhYzgzXHVjNzQwIFx1YzJlMFx1YWNiZFx1YzRmMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjJlOFx1YzljMCBcdWM4MDAgXHVjODE1XHVjYzQ1XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YjM3MFx1YzVkMFx1YjljYyBcdWM5ZDFcdWM5MTFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5Xb3JsZCBGaW5hbCBcdWQ1ODkmbmJzcDtcdWJjODRcdWMyYTRcdWI5N2MgXHVkMGRjXHVjNmI0IFx1YWNiZFx1YjgyNVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMmI5XHVjN2FjXHViMjk0IFx1Yzc3NFx1YmJmOCBcdWIyZjVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1ODhcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjNjNCBcdWIyZjVcdWM3NDQgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMTggbiAoIDMgJmxlOyBuICZsZTsgMjApIFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVjMjE4IG0gKDIgJmxlOyBtICkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKG5cdWM3NDAgXHVkNjM4XHVkMTU0XHVhY2ZjIFx1YWQwMFx1YWQxMVx1YzljMCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YzgxMFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVkM2VjXHVkNTY4XHVkNTVjIFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzgxMFx1Yzc0MCAwfm4tMVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViYTU0XHVhY2E4XHVjOWMwXHViMjk0XHViMzcwLCZuYnNwOzBcdWJjODggXHVjODE1XHVjODEwXHVjNzQwIFx1YmM4NFx1YzJhNFx1Yzc1OCBcdWNkOWNcdWJjMWNcdWM5YzBcdWM4MTBcdWM3NzRcdWFjZTAsIG4tMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVhZDAwXHVhZDExXHVjOWMwLCBcdWIwOThcdWJhMzhcdWM5YzAgMX5uLTJcdWJjODggXHVjODE1XHVjODEwXHVjNzQwIFx1ZDYzOFx1ZDE1NFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IHUsdix0IFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgdSx2ICZsZTsgbi0xLCAxICZsZTsgdCAmbGU7IDM2MDApIFx1Yzc3NFx1YjI5NCB1IHVcdWM1ZDBcdWMxMWMgdlx1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgdFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWUzOFx1Yzc0MCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIHZcdWM1ZDBcdWMxMWMgdVx1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzBcdWM1ZDBcdWIzYzQgdFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODRcdWM3NThcdWM3NTggXHVkNTVjIFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWJkODBcdWQxMzAgXHViMmU0XHViOTc4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0ICZxdW90O0Nhc2UgdDogZCZxdW90OyBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiB0XHViMjk0IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIGRcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWM3NzRcdWIzZDlcdWFjNzBcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDIwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJ1cyBUb3VyIiwiZGVzY3JpcHRpb24iOiI8cD5JbWFnaW5lIHlvdSBhcmUgYSB0b3VyaXN0IGluIFdhcnNhdyBhbmQgaGF2ZSBib29rZWQgYSBidXMgdG91ciB0byBzZWUgc29tZSBhbWF6aW5nIGF0dHJhY3Rpb24ganVzdCBvdXRzaWRlIG9mIHRvd24uIFRoZSBidXMgXHVmYjAxcnN0IGRyaXZlcyBhcm91bmQgdG93biBmb3IgYSB3aGlsZSAoYSBsb25nIHdoaWxlLCBzaW5jZSBXYXJzYXcgaXMgYSBiaWcgY2l0eSkgcGlja2luZyB1cCBwZW9wbGUgYXQgdGhlaXIgcmVzcGVjdGl2ZSBob3RlbHMuIEl0IHRoZW4gcHJvY2VlZHMgdG8gdGhlIGFtYXppbmcgYXR0cmFjdGlvbiwgYW5kIGFmdGVyIGEgZmV3IGhvdXJzIGdvZXMgYmFjayBpbnRvIHRoZSBjaXR5LCBhZ2FpbiBkcml2aW5nIHRvIGVhY2ggaG90ZWwsIHRoaXMgdGltZSB0byBkcm9wIHBlb3BsZSBvZmYuPFwvcD5cclxuXHJcbjxwPkZvciBzb21lIHJlYXNvbiwgd2hlbmV2ZXIgeW91IGRvIHRoaXMsIHlvdXIgaG90ZWwgaXMgYWx3YXlzIHRoZSBcdWZiMDFyc3QgdG8gYmUgdmlzaXRlZCBmb3IgcGlja3VwLCBhbmQgdGhlIGxhc3QgdG8gYmUgdmlzaXRlZCBmb3IgZHJvcG9mZiwgbWVhbmluZyB0aGF0IHlvdSBoYXZlIHRvIHN1ZmZlciB0aHJvdWdoIHR3byBub3Qtc28tYW1hemluZyBzaWdodHNlZWluZyB0b3VycyBvZiBhbGwgdGhlIGxvY2FsIGhvdGVscy4gVGhpcyBpcyBjbGVhcmx5IG5vdCB3aGF0IHlvdSB3YW50IHRvIGRvICh1bmxlc3MgZm9yIHNvbWUgcmVhc29uIHlvdSBhcmUgcmVhbGx5IGludG8gaG90ZWxzKSwgc28gbGV0JnJzcXVvO3MgXHVmYjAxeCBpdC4gV2Ugd2lsbCBkZXZlbG9wIHNvbWUgc29mdHdhcmUgdG8gZW5hYmxlIHRoZSBzaWdodHNlZWluZyBjb21wYW55IHRvIHJvdXRlIGl0cyBidXMgdG91cnMgbW9yZSBmYWlybHktJm1kYXNoO3Rob3VnaCBpdCBtYXkgc29tZXRpbWVzIG1lYW4gbG9uZ2VyIHRvdGFsIGRpc3RhbmNlIGZvciBldmVyeW9uZSwgYnV0IGZhaXIgaXMgZmFpciwgcmlnaHQ/PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHRoZXJlIGlzIGEgc3RhcnRpbmcgbG9jYXRpb24gKHRoZSBzaWdodHNlZWluZyBjb21wYW55IGhlYWRxdWFydGVycyksIGggaG90ZWxzIHRoYXQgbmVlZCB0byBiZSB2aXNpdGVkIGZvciBwaWNrdXBzIGFuZCBkcm9wb2ZmcywgYW5kIGEgZGVzdGluYXRpb24gbG9jYXRpb24gKHRoZSBhbWF6aW5nIGF0dHJhY3Rpb24pLiBXZSBuZWVkIHRvIFx1ZmIwMW5kIGEgcm91dGUgdGhhdCBnb2VzIGZyb20gdGhlIGhlYWRxdWFydGVycywgdGhyb3VnaCBhbGwgdGhlIGhvdGVscywgdG8gdGhlIGF0dHJhY3Rpb24sIHRoZW4gYmFjayB0aHJvdWdoIGFsbCB0aGUgaG90ZWxzIGFnYWluIChwb3NzaWJseSBpbiBhIGRpZmZlcmVudCBvcmRlciksIGFuZCBcdWZiMDFuYWxseSBiYWNrIHRvIHRoZSBoZWFkcXVhcnRlcnMuIEluIG9yZGVyIHRvIGd1YXJhbnRlZSB0aGF0IG5vbmUgb2YgdGhlIHRvdXJpc3RzIChhbmQsIGluIHBhcnRpY3VsYXIsIHlvdSkgYXJlIGZvcmNlZCB0byBzdWZmZXIgdGhyb3VnaCB0d28gZnVsbCB0b3VycyBvZiB0aGUgaG90ZWxzLCB3ZSByZXF1aXJlIHRoYXQgZXZlcnkgaG90ZWwgdGhhdCBpcyB2aXNpdGVkIGFtb25nIHRoZSBcdWZiMDFyc3QgJmxmbG9vcjtoXC8yJnJmbG9vcjsgaG90ZWxzIG9uIHRoZSB3YXkgdG8gdGhlIGF0dHJhY3Rpb24gaXMgYWxzbyB2aXNpdGVkIGFtb25nIHRoZSBcdWZiMDFyc3QgJmxmbG9vcjtiXC8yJnJmbG9vcjsgaG90ZWxzIG9uIHRoZSB3YXkgYmFjay4gU3ViamVjdCB0byB0aGVzZSByZXN0cmljdGlvbnMsIHdlIHdvdWxkIGxpa2UgdG8gbWFrZSB0aGUgY29tcGxldGUgYnVzIHRvdXIgYXMgc2hvcnQgYXMgcG9zc2libGUuIE5vdGUgdGhhdCB0aGVzZSByZXN0cmljdGlvbnMgbWF5IGZvcmNlIHRoZSBidXMgdG8gZHJpdmUgcGFzdCBhIGhvdGVsIHdpdGhvdXQgc3RvcHBpbmcgdGhlcmUgKHRoaXMgaXMgbm90IGNvbnNpZGVyZWQgdmlzaXRpbmcpIGFuZCB0aGVuIHZpc2l0IGl0IGxhdGVyLCBhcyBpbGx1c3RyYXRlZCBpbiB0aGUgXHVmYjAxcnN0IHNhbXBsZSBpbnB1dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgbiBhbmQgbSBzYXRpc2Z5aW5nIDMgJmxlOyBuICZsZTsgMjAgYW5kIDIgJmxlOyBtLCB3aGVyZSBuIGlzIHRoZSBudW1iZXIgb2YgbG9jYXRpb25zIChob3RlbHMsIGhlYWRxdWFydGVycywgYXR0cmFjdGlvbikgYW5kIG0gaXMgdGhlIG51bWJlciBvZiBwYWlycyBvZiBsb2NhdGlvbnMgYmV0d2VlbiB3aGljaCB0aGUgYnVzIGNhbiB0cmF2ZWwuPFwvcD5cclxuXHJcbjxwPlRoZSBuIGRpZmZlcmVudCBsb2NhdGlvbnMgYXJlIG51bWJlcmVkIGZyb20gMCB0byBuLTEsIHdoZXJlIDAgaXMgdGhlIGhlYWRxdWFydGVycywgMSB0aHJvdWdoIG4tMiBhcmUgdGhlIGhvdGVscywgYW5kIG4tMSBpcyB0aGUgYXR0cmFjdGlvbi4gQXNzdW1lIHRoYXQgdGhlcmUgaXMgYXQgbW9zdCBvbmUgZGlyZWN0IGNvbm5lY3Rpb24gYmV0d2VlbiBhbnkgcGFpciBvZiBsb2NhdGlvbnMgYW5kIGl0IGlzIHBvc3NpYmxlIHRvIHRyYXZlbCBmcm9tIGFueSBsb2NhdGlvbiB0byBhbnkgb3RoZXIgbG9jYXRpb24gKGJ1dCBub3QgbmVjZXNzYXJpbHkgZGlyZWN0bHkpLjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhlIFx1ZmIwMXJzdCBsaW5lIGFyZSBtIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgdGhyZWUgaW50ZWdlcnMgdSwgdiwgYW5kIHQgc3VjaCB0aGF0IDAgJmxlOyB1LHYgJmxlOyBuLTEsIHUgJm5lOyB2LCAxICZsZTsgdCAmbGU7IDM2MDAsIGluZGljYXRpbmcgdGhhdCB0aGUgYnVzIGNhbiBnbyBkaXJlY3RseSBiZXR3ZWVuIGxvY2F0aW9ucyB1IGFuZCB2IGluIHQgc2Vjb25kcyAoaW4gZWl0aGVyIGRpcmVjdGlvbikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBkaXNwbGF5IHRoZSBjYXNlIG51bWJlciBhbmQgdGhlIHRpbWUgaW4gc2Vjb25kcyBvZiB0aGUgc2hvcnRlc3QgcG9zc2libGUgdG91ci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > World Finals > ACM-ICPC World Finals 2012 C번