시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWMyYjlcdWM3YWNcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCZuYnNwOyZuYnNwO0FMUFMgXHViY2Y4XHVjMGFjXHVjNWQwXHVjMTFjIFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWQwYzBcdWFjZTAmbmJzcDtcdWNkOWNcdWJjMWNcdWQ1NzQmbmJzcDtoXHVhYzFjXHVjNzU4IFx1ZDYzOFx1ZDE1NFx1YzVkMFx1YzExYyBcdWFkMDBcdWFkMTFcdWFjMWRcdWI0ZTRcdWM3NDQgXHVkNTVjXHViYTg1XHVjNTI5IHBpY2sgdXAgXHVkNTc0XHVjMTFjIFx1YWQwMFx1YWQxMVx1YzljMFx1YzVkMCBcdWIzNzBcdWI4MjRcdWIyZTQgXHVjOTAwIFx1YjRhNCwgXHVhZGY4XHViNGU0XHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWM2ZDBcdWI3OTggXHVkNjM4XHVkMTU0XHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YWNlMCBBTFBTIFx1YmNmOFx1YzBhY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVjNzdjXHVjNzc0XHViMmU0LiBBTFBTXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCZuYnNwO1x1YWQwMFx1YWQxMVx1YzljMFx1YjI5NCZuYnNwO0FDTShBbWF6aW5nIENvbW1vbiBNb3VudGFpbikgXHViZmQwXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFkMDBcdWFkMTFcdWM5YzBcdWIyOTQmbmJzcDtcdWIyOTggQUNNJm5ic3A7XHVkNTVjIFx1YWNmM1x1YjljY1x1Yzc0NCBcdWI0NThcdWI3ZWNcdWJjZjRcdWJhNzQgXHViNDFjXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QUxQU1x1YjI5NCBcdWMxMWNcdWJlNDRcdWMyYTRcdWM4MTVcdWMyZTBcdWM3NzQgXHViNmYwXHVjNWI0XHViMDljIFx1ZDY4Y1x1YzBhY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIHBpY2sgdXBcdWM3NDQgXHViYTNjXHVjODAwIFx1ZDU1YyBcdWFkMDBcdWFkMTFcdWFjMWRcdWI0ZTRcdWJkODBcdWQxMzAgXHVkNjM4XHVkMTU0XHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YjgyNFx1YWNlMCBcdWIxNzhcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWJhM2NcdWM4MDAgcGljayB1cFx1YjQxYyBcdWFkMDBcdWFkMTFcdWFjMWRcdWM3NzQgXHViMGE4XHViNGU0XHViY2Y0XHViMmU0IFx1YjJhNlx1YWM4YyBcdWIwYjRcdWI5YjBcdWIyZTRcdWJhNzQgXHVhZGY4XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNjMjhcdWJjYzRcdWIzMDBcdWM2YjBcdWI5N2MgXHViYzFiXHVhY2UwXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU2MCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1ZDU2ZFx1Yzc1OFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTRcdWJhNzQgQUxQU1x1YjI5NCBcdWI5ZGRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LikgXHVjNzc0XHVjNWQwIEFMUFNcdWIyOTQgXHVjNzkwXHVjMmUwXHViOWNjXHVjNzU4IHBpY2sgdXAgXHVjODE1XHVjYzQ1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+aFx1YWMxY1x1Yzc1OCBcdWQ2MzhcdWQxNTRcdWM1ZDBcdWMxMWMgXHVhZDAwXHVhZDExXHVhYzFkXHViNGU0XHVjNzQ0IHBpY2sgdXAgXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCwgaFwvMlx1YmM4OFx1YzlmOCBcdWMyMWNcdWMxMWMmbmJzcDtcdWM3NzRcdWIwYjRcdWI4NWMgcGljayB1cFx1ZDU1YyBcdWFkMDBcdWFkMTFcdWFjMWRcdWI0ZTRcdWM3NDAgXHVhZDAwXHVhZDExXHVjNzc0IFx1YjA1ZFx1YjA5YyBcdWI0YTQgXHVkNjM4XHVkMTU0XHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNCBcdWM5MDQgXHViNTRjXHViM2M0IGhcLzJcdWJjODhcdWM5ZjggXHVjMjFjXHVjMTFjIFx1Yzc3NFx1YjBiNFx1Yjg1YyBcdWQ2MzhcdWQxNTRcdWI4NWMgXHViM2NjXHViODI0XHViY2Y0XHViMGI0XHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM4MTVcdWNjNDVcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPihcdWM5ODksIDEgMiAzIDQgNSBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgcGljayB1cCBcdWQ1ODhcdWIyZTRcdWJhNzQgXHViM2NjXHVjNTQ0XHVjNjJjIFx1YjU0YyAyIDEgMyA0IDUgXHViMDk4IDEgMiA1IDMgNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHViM2NjXHViODI0XHViY2Y0XHViMGI0XHVjOGZjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NThcdWM5YzBcdWI5Y2MgMSAzIDIgNCA1IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWIzY2NcdWI4MjRcdWJjZjRcdWIwYjRcdWM4ZmNcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiAyXHViYzg4XHVjOWY4XHViODVjIHBpY2sgdXAgXHViNDFjIFx1YWQwMFx1YWQxMVx1YWMxZFx1Yzc3NCA1XC8yXHViY2Y0XHViMmU0IFx1ZDA3MCAzXHViYzg4XHVjOWY4XHViODVjIFx1YjBiNFx1YjgzOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWMyYjlcdWM3YWNcdWIyOTQgXHViYzg0XHVjMmE0XHVjNzU4IFx1YWUzMFx1Yjk4NFx1YWMxMlx1Yzc0NCBcdWM1NDRcdWIwN2NcdWFjZTAgXHVjMmY2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCZuYnNwO1x1ZDU1OFx1YjhlOFx1YjNkOVx1YzU0OCBcdWJjODRcdWMyYTRcdWFjMDAmbmJzcDtcdWM2YzBcdWM5YzFcdWM1ZWNcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyZuYnNwO1x1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBBTFBTIFx1YmNmOFx1YzBhY1x1YzY0MCBcdWQ2MzhcdWQxNTRcdWI0ZTQsIFx1YWRmOFx1YjlhY1x1YWNlMCBBQ00gXHVhZDAwXHVhZDExXHVjOWMwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjODE1XHVjYzQ1XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyBcdWJjODRcdWMyYTRcdWFjMDAgXHVjNmMwXHVjOWMxXHVjNWVjXHVjNTdjXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM3NzQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWNjNDVcdWM1ZDBcdWIyOTQgXHVhZDAwXHVhZDExXHVhYzFkXHVjNzQ0IFx1ZDBkY1x1YzZiMFx1YWNlMCBcdWIwYjRcdWI5YWNcdWIyOTQgXHVjMjFjXHVjMTFjXHViOWNjIFx1YzgxNVx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzc0IFx1YzgxNVx1Y2M0NVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVhYzAwIFx1YzU0OFx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWM1YjRcdWNhNTRcdWI1NGNcdWIyOTQgXHVkNjM4XHVkMTU0XHVjNzQ0IFx1YWRmOFx1YjBlNSBcdWM5YzBcdWIwOThcdWNjZDBcdWM1N2NcdWQ1NThcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YzYyYyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgQUxQU1x1YjI5NCBcdWFkZjhcdWI3ZjAgJiMzOTtcdWMwYWNcdWMxOGNcdWQ1NWMmIzM5O1x1YWM4M1x1Yzc0MCBcdWMyZTBcdWFjYmRcdWM0ZjBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWIyZThcdWM5YzAgXHVjODAwIFx1YzgxNVx1Y2M0NVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWIzNzBcdWM1ZDBcdWI5Y2MgXHVjOWQxXHVjOTExXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+V29ybGQgRmluYWwgXHVkNTg5Jm5ic3A7XHViYzg0XHVjMmE0XHViOTdjIFx1ZDBkY1x1YzZiNCBcdWFjYmRcdWI4MjVcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzJiOVx1YzdhY1x1YjI5NCBcdWM3NzRcdWJiZjggXHViMmY1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIzYzQgXHViMmY1XHVjNzQ0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4IG4gKCAzICZsZTsgbiAmbGU7IDIwKSBcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOCBtICgyICZsZTsgbSApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuXHVjNzQwIFx1ZDYzOFx1ZDE1NFx1YWNmYyBcdWFkMDBcdWFkMTFcdWM5YzAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNkOWNcdWJjMWNcdWM5YzBcdWM4MTBcdWM3NDQgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OFx1ZDU1YyBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM4MTBcdWM3NDAgMH5uLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmE1NFx1YWNhOFx1YzljMFx1YjI5NFx1YjM3MCwmbmJzcDswXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWJjODRcdWMyYTRcdWM3NTggXHVjZDljXHViYzFjXHVjOWMwXHVjODEwXHVjNzc0XHVhY2UwLCBuLTFcdWJjODggXHVjODE1XHVjODEwXHVjNzQwIFx1YWQwMFx1YWQxMVx1YzljMCwgXHViMDk4XHViYTM4XHVjOWMwIDF+bi0yXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWQ2MzhcdWQxNTRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWMxMWMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YzgxNVx1YzIxOCB1LHYsdCBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHUsdiAmbGU7IG4tMSwgMSAmbGU7IHQgJmxlOyAzNjAwKSBcdWM3NzRcdWIyOTQgdSB1XHVjNWQwXHVjMTFjIHZcdWI4NWMgXHVhYzAwXHViMjk0XHViMzcwIHRcdWI5Y2NcdWQwN2NcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFlMzhcdWM3NDAgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCB2XHVjNWQwXHVjMTFjIHVcdWI4NWMgXHVhYzAwXHViMjk0XHViMzcwXHVjNWQwXHViM2M0IHRcdWI5Y2NcdWQwN2NcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHViZDgwXHVkMTMwIFx1YjJlNFx1Yjk3OCBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtDYXNlIHQ6IGQmcXVvdDsgXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gdFx1YjI5NCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBkXHViMjk0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjNzc0XHViM2Q5XHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyMDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdXMgVG91ciIsImRlc2NyaXB0aW9uIjoiPHA+SW1hZ2luZSB5b3UgYXJlIGEgdG91cmlzdCBpbiBXYXJzYXcgYW5kIGhhdmUgYm9va2VkIGEgYnVzIHRvdXIgdG8gc2VlIHNvbWUgYW1hemluZyBhdHRyYWN0aW9uIGp1c3Qgb3V0c2lkZSBvZiB0b3duLiBUaGUgYnVzIFx1ZmIwMXJzdCBkcml2ZXMgYXJvdW5kIHRvd24gZm9yIGEgd2hpbGUgKGEgbG9uZyB3aGlsZSwgc2luY2UgV2Fyc2F3IGlzIGEgYmlnIGNpdHkpIHBpY2tpbmcgdXAgcGVvcGxlIGF0IHRoZWlyIHJlc3BlY3RpdmUgaG90ZWxzLiBJdCB0aGVuIHByb2NlZWRzIHRvIHRoZSBhbWF6aW5nIGF0dHJhY3Rpb24sIGFuZCBhZnRlciBhIGZldyBob3VycyBnb2VzIGJhY2sgaW50byB0aGUgY2l0eSwgYWdhaW4gZHJpdmluZyB0byBlYWNoIGhvdGVsLCB0aGlzIHRpbWUgdG8gZHJvcCBwZW9wbGUgb2ZmLjxcL3A+XHJcblxyXG48cD5Gb3Igc29tZSByZWFzb24sIHdoZW5ldmVyIHlvdSBkbyB0aGlzLCB5b3VyIGhvdGVsIGlzIGFsd2F5cyB0aGUgXHVmYjAxcnN0IHRvIGJlIHZpc2l0ZWQgZm9yIHBpY2t1cCwgYW5kIHRoZSBsYXN0IHRvIGJlIHZpc2l0ZWQgZm9yIGRyb3BvZmYsIG1lYW5pbmcgdGhhdCB5b3UgaGF2ZSB0byBzdWZmZXIgdGhyb3VnaCB0d28gbm90LXNvLWFtYXppbmcgc2lnaHRzZWVpbmcgdG91cnMgb2YgYWxsIHRoZSBsb2NhbCBob3RlbHMuIFRoaXMgaXMgY2xlYXJseSBub3Qgd2hhdCB5b3Ugd2FudCB0byBkbyAodW5sZXNzIGZvciBzb21lIHJlYXNvbiB5b3UgYXJlIHJlYWxseSBpbnRvIGhvdGVscyksIHNvIGxldCZyc3F1bztzIFx1ZmIwMXggaXQuIFdlIHdpbGwgZGV2ZWxvcCBzb21lIHNvZnR3YXJlIHRvIGVuYWJsZSB0aGUgc2lnaHRzZWVpbmcgY29tcGFueSB0byByb3V0ZSBpdHMgYnVzIHRvdXJzIG1vcmUgZmFpcmx5LSZtZGFzaDt0aG91Z2ggaXQgbWF5IHNvbWV0aW1lcyBtZWFuIGxvbmdlciB0b3RhbCBkaXN0YW5jZSBmb3IgZXZlcnlvbmUsIGJ1dCBmYWlyIGlzIGZhaXIsIHJpZ2h0PzxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB0aGVyZSBpcyBhIHN0YXJ0aW5nIGxvY2F0aW9uICh0aGUgc2lnaHRzZWVpbmcgY29tcGFueSBoZWFkcXVhcnRlcnMpLCBoIGhvdGVscyB0aGF0IG5lZWQgdG8gYmUgdmlzaXRlZCBmb3IgcGlja3VwcyBhbmQgZHJvcG9mZnMsIGFuZCBhIGRlc3RpbmF0aW9uIGxvY2F0aW9uICh0aGUgYW1hemluZyBhdHRyYWN0aW9uKS4gV2UgbmVlZCB0byBcdWZiMDFuZCBhIHJvdXRlIHRoYXQgZ29lcyBmcm9tIHRoZSBoZWFkcXVhcnRlcnMsIHRocm91Z2ggYWxsIHRoZSBob3RlbHMsIHRvIHRoZSBhdHRyYWN0aW9uLCB0aGVuIGJhY2sgdGhyb3VnaCBhbGwgdGhlIGhvdGVscyBhZ2FpbiAocG9zc2libHkgaW4gYSBkaWZmZXJlbnQgb3JkZXIpLCBhbmQgXHVmYjAxbmFsbHkgYmFjayB0byB0aGUgaGVhZHF1YXJ0ZXJzLiBJbiBvcmRlciB0byBndWFyYW50ZWUgdGhhdCBub25lIG9mIHRoZSB0b3VyaXN0cyAoYW5kLCBpbiBwYXJ0aWN1bGFyLCB5b3UpIGFyZSBmb3JjZWQgdG8gc3VmZmVyIHRocm91Z2ggdHdvIGZ1bGwgdG91cnMgb2YgdGhlIGhvdGVscywgd2UgcmVxdWlyZSB0aGF0IGV2ZXJ5IGhvdGVsIHRoYXQgaXMgdmlzaXRlZCBhbW9uZyB0aGUgXHVmYjAxcnN0ICZsZmxvb3I7aFwvMiZyZmxvb3I7IGhvdGVscyBvbiB0aGUgd2F5IHRvIHRoZSBhdHRyYWN0aW9uIGlzIGFsc28gdmlzaXRlZCBhbW9uZyB0aGUgXHVmYjAxcnN0ICZsZmxvb3I7YlwvMiZyZmxvb3I7IGhvdGVscyBvbiB0aGUgd2F5IGJhY2suIFN1YmplY3QgdG8gdGhlc2UgcmVzdHJpY3Rpb25zLCB3ZSB3b3VsZCBsaWtlIHRvIG1ha2UgdGhlIGNvbXBsZXRlIGJ1cyB0b3VyIGFzIHNob3J0IGFzIHBvc3NpYmxlLiBOb3RlIHRoYXQgdGhlc2UgcmVzdHJpY3Rpb25zIG1heSBmb3JjZSB0aGUgYnVzIHRvIGRyaXZlIHBhc3QgYSBob3RlbCB3aXRob3V0IHN0b3BwaW5nIHRoZXJlICh0aGlzIGlzIG5vdCBjb25zaWRlcmVkIHZpc2l0aW5nKSBhbmQgdGhlbiB2aXNpdCBpdCBsYXRlciwgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIFx1ZmIwMXJzdCBzYW1wbGUgaW5wdXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIG4gYW5kIG0gc2F0aXNmeWluZyAzICZsZTsgbiAmbGU7IDIwIGFuZCAyICZsZTsgbSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIGxvY2F0aW9ucyAoaG90ZWxzLCBoZWFkcXVhcnRlcnMsIGF0dHJhY3Rpb24pIGFuZCBtIGlzIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgbG9jYXRpb25zIGJldHdlZW4gd2hpY2ggdGhlIGJ1cyBjYW4gdHJhdmVsLjxcL3A+XHJcblxyXG48cD5UaGUgbiBkaWZmZXJlbnQgbG9jYXRpb25zIGFyZSBudW1iZXJlZCBmcm9tIDAgdG8gbi0xLCB3aGVyZSAwIGlzIHRoZSBoZWFkcXVhcnRlcnMsIDEgdGhyb3VnaCBuLTIgYXJlIHRoZSBob3RlbHMsIGFuZCBuLTEgaXMgdGhlIGF0dHJhY3Rpb24uIEFzc3VtZSB0aGF0IHRoZXJlIGlzIGF0IG1vc3Qgb25lIGRpcmVjdCBjb25uZWN0aW9uIGJldHdlZW4gYW55IHBhaXIgb2YgbG9jYXRpb25zIGFuZCBpdCBpcyBwb3NzaWJsZSB0byB0cmF2ZWwgZnJvbSBhbnkgbG9jYXRpb24gdG8gYW55IG90aGVyIGxvY2F0aW9uIChidXQgbm90IG5lY2Vzc2FyaWx5IGRpcmVjdGx5KS48XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIHRoZSBcdWZiMDFyc3QgbGluZSBhcmUgbSBsaW5lcywgZWFjaCBjb250YWluaW5nIHRocmVlIGludGVnZXJzIHUsIHYsIGFuZCB0IHN1Y2ggdGhhdCAwICZsZTsgdSx2ICZsZTsgbi0xLCB1ICZuZTsgdiwgMSAmbGU7IHQgJmxlOyAzNjAwLCBpbmRpY2F0aW5nIHRoYXQgdGhlIGJ1cyBjYW4gZ28gZGlyZWN0bHkgYmV0d2VlbiBsb2NhdGlvbnMgdSBhbmQgdiBpbiB0IHNlY29uZHMgKGluIGVpdGhlciBkaXJlY3Rpb24pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSB0aGUgY2FzZSBudW1iZXIgYW5kIHRoZSB0aW1lIGluIHNlY29uZHMgb2YgdGhlIHNob3J0ZXN0IHBvc3NpYmxlIHRvdXIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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