시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 78 22 16 27.586%

문제

승재는 유명한 관광회사 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+XHJcblxyXG48cD4oXHVjOTg5LCAxIDIgMyA0IDUgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIHBpY2sgdXAgXHVkNTg4XHViMmU0XHViYTc0IFx1YjNjY1x1YzU0NFx1YzYyYyBcdWI1NGMgMiAxIDMgNCA1IFx1YjA5OCAxIDIgNSAzIDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YzhmY1x1YjI5NCBcdWFjODNcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTU4XHVjOWMwXHViOWNjIDEgMyAyIDQgNSBcdWMyMWNcdWM3M2NcdWI4NWMgXHViM2NjXHViODI0XHViY2Y0XHViMGI0XHVjOGZjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gMlx1YmM4OFx1YzlmOFx1Yjg1YyBwaWNrIHVwIFx1YjQxYyBcdWFkMDBcdWFkMTFcdWFjMWRcdWM3NzQgNVwvMlx1YmNmNFx1YjJlNCBcdWQwNzAgM1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWIwYjRcdWI4MzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjMmI5XHVjN2FjXHViMjk0IFx1YmM4NFx1YzJhNFx1Yzc1OCBcdWFlMzBcdWI5ODRcdWFjMTJcdWM3NDQgXHVjNTQ0XHViMDdjXHVhY2UwIFx1YzJmNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWQ1NThcdWI4ZThcdWIzZDlcdWM1NDggXHViYzg0XHVjMmE0XHVhYzAwJm5ic3A7XHVjNmMwXHVjOWMxXHVjNWVjXHVjNTdjXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MmbmJzcDtcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1Yzg0Y1x1YjJlNC4gQUxQUyBcdWJjZjhcdWMwYWNcdWM2NDAgXHVkNjM4XHVkMTU0XHViNGU0LCBcdWFkZjhcdWI5YWNcdWFjZTAgQUNNIFx1YWQwMFx1YWQxMVx1YzljMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzgxNVx1Y2M0NVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzRcdWMxMWMgXHViYzg0XHVjMmE0XHVhYzAwIFx1YzZjMFx1YzljMVx1YzVlY1x1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjYzQ1XHVjNWQwXHViMjk0IFx1YWQwMFx1YWQxMVx1YWMxZFx1Yzc0NCBcdWQwZGNcdWM2YjBcdWFjZTAgXHViMGI0XHViOWFjXHViMjk0IFx1YzIxY1x1YzExY1x1YjljYyBcdWM4MTVcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc3NCBcdWM4MTVcdWNjNDVcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM1NDhcdWI0MjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjNWI0XHVjYTU0XHViNTRjXHViMjk0IFx1ZDYzOFx1ZDE1NFx1Yzc0NCBcdWFkZjhcdWIwZTUgXHVjOWMwXHViMDk4XHVjY2QwXHVjNTdjXHVkNTU4XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWM2MmMgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIEFMUFNcdWIyOTQgXHVhZGY4XHViN2YwICYjMzk7XHVjMGFjXHVjMThjXHVkNTVjJiMzOTtcdWFjODNcdWM3NDAgXHVjMmUwXHVhY2JkXHVjNGYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViMmU4XHVjOWMwIFx1YzgwMCBcdWM4MTVcdWNjNDVcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHViMzcwXHVjNWQwXHViOWNjIFx1YzlkMVx1YzkxMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPldvcmxkIEZpbmFsIFx1ZDU4OSZuYnNwO1x1YmM4NFx1YzJhNFx1Yjk3YyBcdWQwZGNcdWM2YjQgXHVhY2JkXHViODI1XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWMyYjlcdWM3YWNcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU4OFx1YjJlNC4gXHVjNmIwXHViOWFjXHViM2M0IFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM5OWRcdWJhODVcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOCBuICggMyAmbGU7IG4gJmxlOyAyMCkgXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMTggbSAoMiAmbGU7IG0gKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoblx1Yzc0MCBcdWQ2MzhcdWQxNTRcdWFjZmMgXHVhZDAwXHVhZDExXHVjOWMwLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjZDljXHViYzFjXHVjOWMwXHVjODEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWQ1NWMgXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjODEwXHVjNzQwIDB+bi0xXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJhNTRcdWFjYThcdWM5YzBcdWIyOTRcdWIzNzAsJm5ic3A7MFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViYzg0XHVjMmE0XHVjNzU4IFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YzgxMFx1Yzc3NFx1YWNlMCwgbi0xXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWFkMDBcdWFkMTFcdWM5YzAsIFx1YjA5OFx1YmEzOFx1YzljMCAxfm4tMlx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVkNjM4XHVkMTU0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjMTFjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWM4MTVcdWMyMTggdSx2LHQgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyB1LHYgJmxlOyBuLTEsIDEgJmxlOyB0ICZsZTsgMzYwMCkgXHVjNzc0XHViMjk0IHUgdVx1YzVkMFx1YzExYyB2XHViODVjIFx1YWMwMFx1YjI5NFx1YjM3MCB0XHViOWNjXHVkMDdjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVhZTM4XHVjNzQwIFx1YzU5MVx1YmMyOVx1ZDVhNVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgdlx1YzVkMFx1YzExYyB1XHViODVjIFx1YWMwMFx1YjI5NFx1YjM3MFx1YzVkMFx1YjNjNCB0XHViOWNjXHVkMDdjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NWMgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YmQ4MFx1ZDEzMCBcdWIyZTRcdWI5NzggXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NzRcdWIzYzQgXHVjODhiXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7Q2FzZSB0OiBkJnF1b3Q7IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIHRcdWIyOTQgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCwgZFx1YjI5NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhY2JkXHViODVjXHVjNzU4IFx1Yzc3NFx1YjNkOVx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnVzIFRvdXIiLCJkZXNjcmlwdGlvbiI6IjxwPkltYWdpbmUgeW91IGFyZSBhIHRvdXJpc3QgaW4gV2Fyc2F3IGFuZCBoYXZlIGJvb2tlZCBhIGJ1cyB0b3VyIHRvIHNlZSBzb21lIGFtYXppbmcgYXR0cmFjdGlvbiBqdXN0IG91dHNpZGUgb2YgdG93bi4gVGhlIGJ1cyBcdWZiMDFyc3QgZHJpdmVzIGFyb3VuZCB0b3duIGZvciBhIHdoaWxlIChhIGxvbmcgd2hpbGUsIHNpbmNlIFdhcnNhdyBpcyBhIGJpZyBjaXR5KSBwaWNraW5nIHVwIHBlb3BsZSBhdCB0aGVpciByZXNwZWN0aXZlIGhvdGVscy4gSXQgdGhlbiBwcm9jZWVkcyB0byB0aGUgYW1hemluZyBhdHRyYWN0aW9uLCBhbmQgYWZ0ZXIgYSBmZXcgaG91cnMgZ29lcyBiYWNrIGludG8gdGhlIGNpdHksIGFnYWluIGRyaXZpbmcgdG8gZWFjaCBob3RlbCwgdGhpcyB0aW1lIHRvIGRyb3AgcGVvcGxlIG9mZi48XC9wPlxyXG5cclxuPHA+Rm9yIHNvbWUgcmVhc29uLCB3aGVuZXZlciB5b3UgZG8gdGhpcywgeW91ciBob3RlbCBpcyBhbHdheXMgdGhlIFx1ZmIwMXJzdCB0byBiZSB2aXNpdGVkIGZvciBwaWNrdXAsIGFuZCB0aGUgbGFzdCB0byBiZSB2aXNpdGVkIGZvciBkcm9wb2ZmLCBtZWFuaW5nIHRoYXQgeW91IGhhdmUgdG8gc3VmZmVyIHRocm91Z2ggdHdvIG5vdC1zby1hbWF6aW5nIHNpZ2h0c2VlaW5nIHRvdXJzIG9mIGFsbCB0aGUgbG9jYWwgaG90ZWxzLiBUaGlzIGlzIGNsZWFybHkgbm90IHdoYXQgeW91IHdhbnQgdG8gZG8gKHVubGVzcyBmb3Igc29tZSByZWFzb24geW91IGFyZSByZWFsbHkgaW50byBob3RlbHMpLCBzbyBsZXQmcnNxdW87cyBcdWZiMDF4IGl0LiBXZSB3aWxsIGRldmVsb3Agc29tZSBzb2Z0d2FyZSB0byBlbmFibGUgdGhlIHNpZ2h0c2VlaW5nIGNvbXBhbnkgdG8gcm91dGUgaXRzIGJ1cyB0b3VycyBtb3JlIGZhaXJseS0mbWRhc2g7dGhvdWdoIGl0IG1heSBzb21ldGltZXMgbWVhbiBsb25nZXIgdG90YWwgZGlzdGFuY2UgZm9yIGV2ZXJ5b25lLCBidXQgZmFpciBpcyBmYWlyLCByaWdodD88XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgdGhlcmUgaXMgYSBzdGFydGluZyBsb2NhdGlvbiAodGhlIHNpZ2h0c2VlaW5nIGNvbXBhbnkgaGVhZHF1YXJ0ZXJzKSwgaCBob3RlbHMgdGhhdCBuZWVkIHRvIGJlIHZpc2l0ZWQgZm9yIHBpY2t1cHMgYW5kIGRyb3BvZmZzLCBhbmQgYSBkZXN0aW5hdGlvbiBsb2NhdGlvbiAodGhlIGFtYXppbmcgYXR0cmFjdGlvbikuIFdlIG5lZWQgdG8gXHVmYjAxbmQgYSByb3V0ZSB0aGF0IGdvZXMgZnJvbSB0aGUgaGVhZHF1YXJ0ZXJzLCB0aHJvdWdoIGFsbCB0aGUgaG90ZWxzLCB0byB0aGUgYXR0cmFjdGlvbiwgdGhlbiBiYWNrIHRocm91Z2ggYWxsIHRoZSBob3RlbHMgYWdhaW4gKHBvc3NpYmx5IGluIGEgZGlmZmVyZW50IG9yZGVyKSwgYW5kIFx1ZmIwMW5hbGx5IGJhY2sgdG8gdGhlIGhlYWRxdWFydGVycy4gSW4gb3JkZXIgdG8gZ3VhcmFudGVlIHRoYXQgbm9uZSBvZiB0aGUgdG91cmlzdHMgKGFuZCwgaW4gcGFydGljdWxhciwgeW91KSBhcmUgZm9yY2VkIHRvIHN1ZmZlciB0aHJvdWdoIHR3byBmdWxsIHRvdXJzIG9mIHRoZSBob3RlbHMsIHdlIHJlcXVpcmUgdGhhdCBldmVyeSBob3RlbCB0aGF0IGlzIHZpc2l0ZWQgYW1vbmcgdGhlIFx1ZmIwMXJzdCAmbGZsb29yO2hcLzImcmZsb29yOyBob3RlbHMgb24gdGhlIHdheSB0byB0aGUgYXR0cmFjdGlvbiBpcyBhbHNvIHZpc2l0ZWQgYW1vbmcgdGhlIFx1ZmIwMXJzdCAmbGZsb29yO2JcLzImcmZsb29yOyBob3RlbHMgb24gdGhlIHdheSBiYWNrLiBTdWJqZWN0IHRvIHRoZXNlIHJlc3RyaWN0aW9ucywgd2Ugd291bGQgbGlrZSB0byBtYWtlIHRoZSBjb21wbGV0ZSBidXMgdG91ciBhcyBzaG9ydCBhcyBwb3NzaWJsZS4gTm90ZSB0aGF0IHRoZXNlIHJlc3RyaWN0aW9ucyBtYXkgZm9yY2UgdGhlIGJ1cyB0byBkcml2ZSBwYXN0IGEgaG90ZWwgd2l0aG91dCBzdG9wcGluZyB0aGVyZSAodGhpcyBpcyBub3QgY29uc2lkZXJlZCB2aXNpdGluZykgYW5kIHRoZW4gdmlzaXQgaXQgbGF0ZXIsIGFzIGlsbHVzdHJhdGVkIGluIHRoZSBcdWZiMDFyc3Qgc2FtcGxlIGlucHV0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBuIGFuZCBtIHNhdGlzZnlpbmcgMyAmbGU7IG4gJmxlOyAyMCBhbmQgMiAmbGU7IG0sIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBsb2NhdGlvbnMgKGhvdGVscywgaGVhZHF1YXJ0ZXJzLCBhdHRyYWN0aW9uKSBhbmQgbSBpcyB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGxvY2F0aW9ucyBiZXR3ZWVuIHdoaWNoIHRoZSBidXMgY2FuIHRyYXZlbC48XC9wPlxyXG5cclxuPHA+VGhlIG4gZGlmZmVyZW50IGxvY2F0aW9ucyBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIG4tMSwgd2hlcmUgMCBpcyB0aGUgaGVhZHF1YXJ0ZXJzLCAxIHRocm91Z2ggbi0yIGFyZSB0aGUgaG90ZWxzLCBhbmQgbi0xIGlzIHRoZSBhdHRyYWN0aW9uLiBBc3N1bWUgdGhhdCB0aGVyZSBpcyBhdCBtb3N0IG9uZSBkaXJlY3QgY29ubmVjdGlvbiBiZXR3ZWVuIGFueSBwYWlyIG9mIGxvY2F0aW9ucyBhbmQgaXQgaXMgcG9zc2libGUgdG8gdHJhdmVsIGZyb20gYW55IGxvY2F0aW9uIHRvIGFueSBvdGhlciBsb2NhdGlvbiAoYnV0IG5vdCBuZWNlc3NhcmlseSBkaXJlY3RseSkuPFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyB0aGUgXHVmYjAxcnN0IGxpbmUgYXJlIG0gbGluZXMsIGVhY2ggY29udGFpbmluZyB0aHJlZSBpbnRlZ2VycyB1LCB2LCBhbmQgdCBzdWNoIHRoYXQgMCAmbGU7IHUsdiAmbGU7IG4tMSwgdSAmbmU7IHYsIDEgJmxlOyB0ICZsZTsgMzYwMCwgaW5kaWNhdGluZyB0aGF0IHRoZSBidXMgY2FuIGdvIGRpcmVjdGx5IGJldHdlZW4gbG9jYXRpb25zIHUgYW5kIHYgaW4gdCBzZWNvbmRzIChpbiBlaXRoZXIgZGlyZWN0aW9uKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgdGhlIGNhc2UgbnVtYmVyIGFuZCB0aGUgdGltZSBpbiBzZWNvbmRzIG9mIHRoZSBzaG9ydGVzdCBwb3NzaWJsZSB0b3VyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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