시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 6 5 55.556%

문제

상근이와 선영이는 보스턴 마라톤에 참가하기 위해 열심히 훈련하고 있다. 대회가 얼마 남지 않았기 때문에, 오늘은 훈련 계획을 세워보려고 한다.

두 사람이 살고있는 나라에는 도시가 N개, 도로가 M개 있다. 모든 도로는 두 도시를 연결하며, 양방향으로 이동할 수 있다. 도로 중에서 N-1개는 포장되어 있고, 나머지는 포장되어 있지 않다.

한 도시에서 다른 도시로 이동할 때, 항상 포장된 도로만을 사용해서 이동할 수 있다. 즉, N개의 도시와 N-1개의 포장된 도로는 트리 구조를 이루고 있다.

또, 한 도시와 연결되어 있는 도로는 최대 10개이다.

마라톤 훈련은 도시에서 시작해서, 도로를 돌아다닌 다음, 시작한 도시로 다시 돌아와서 끝난다. 상근이와 선영이는 훈련하면서 아름다운 풍경도 감상하려고 한다. 따라서, 그들은 이미 지나간 도시를 다시 지나가지 않을 것이고, 지난 도로도 다시 지나지 않을 것이다.

훈련을 시작 하는 도시는 어느곳이 되어도 상관없고, 모든 도시를 방문하지 않아도 된다.

뒤에서 달리는 것이 앞에서 달리는 것보다 더 편하다. 그 이유는 앞에서 달리는 사람이 바람을 막아주기 때문이다. 따라서, 상근이와 선영이는 도시에 들어갈 때 마다 자리를 서로 바꿀 것이다. 또, 서로 훈련한 양이 같아야 하기 때문에 짝수 개의 도로를 지나려고 한다.

상근이와 선영이의 경쟁자 상덕이와 희원이는 위의 조건을 만족시키는 경로를 없애기 위해 포장되어 있지 않은 도로의 일부를 폭파시키기로 했다. 각각의 포장되어 있지 않은 도로를 폭파시키는 비용은 입력으로 주어진다. (비용은 양수) 또, 포장된 도로는 폭파시킬 수 없다.

도시와 도로 네트워크가 주어졌을 때, 상근이와 선영이의 훈련 조건을 만족시키는 경로가 없게하기 위해서 필요한 폭파 비용의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N과 도로의 수 M이 주어진다. (2 ≤ N ≤ 1,000, N-1 ≤ M ≤ 5,000)

다음 M개 줄에는 A, B, C가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ C ≤ 10,000) A와 B는 서로 다르며, 도로가 연결하는 도시를 나타낸다. C가 0인 경우는 포장된 도로이다. 포장되어 있지 않은 도로인 경우에는 C값이 양수이며, 이 값은 그 도로를 폭파시키는데 필요한 비용이다.

모든 도시는 많아야 10개 도로와 연결되어져 있다. 또, 한 도시 쌍을 연결하는 도로는 한 개를 넘지 않는다.

출력

첫째 줄에 상근이와 선영이의 훈련 조건을 만족시키는 경로를 없애기 위한 폭파 비용의 최소값을 출력한다.

예제 입력 1

5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1

예제 출력 1

5

힌트

위의 그림은 예제를 그래프로 나타낸 것이다. 굵은 도로는 포장된 도로이다.

상근이와 선영이의 훈련 조건을 만족 시키는 경로는 위와 같이 다섯 가지가 있다. 만약, 도로 1-3, 3-5, 2-5를 폭파시킨다면, 상근이와 선영이는 훈련을 할 수 없다. 이 때, 총 폭파 비용은 5이다.

도로 2-4와 2-5를 폭파시켜도 된다. 하지만, 총 폭파 비용이 6이 된다. 

W3sicHJvYmxlbV9pZCI6IjU0NzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWI3N2NcdWQxYTQgXHVkNmM4XHViODI4IFx1YmMyOVx1ZDU3NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJjZjRcdWMyYTRcdWQxMzQgXHViOWM4XHViNzdjXHVkMWE0XHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDZjOFx1YjgyOFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjMwMFx1ZDY4Y1x1YWMwMCBcdWM1YmNcdWI5YzggXHViMGE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzYyNFx1YjI5OFx1Yzc0MCBcdWQ2YzhcdWI4MjggXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzEzOFx1YzZjY1x1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGI0XHVhY2UwXHVjNzg4XHViMjk0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgTlx1YWMxYywgXHViM2M0XHViODVjXHVhYzAwIE1cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViMjk0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwLCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1Yjg1YyBcdWM5MTFcdWM1ZDBcdWMxMWMgTi0xXHVhYzFjXHViMjk0IFx1ZDNlY1x1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWQzZWNcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViM2M0XHVjMmRjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGMsIFx1ZDU2ZFx1YzBjMSBcdWQzZWNcdWM3YTVcdWI0MWMgXHViM2M0XHViODVjXHViOWNjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBOLTFcdWFjMWNcdWM3NTggXHVkM2VjXHVjN2E1XHViNDFjIFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWQyYjhcdWI5YWMgXHVhZDZjXHVjODcwXHViOTdjIFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMCwgXHVkNTVjIFx1YjNjNFx1YzJkY1x1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWNkNWNcdWIzMDAgMTBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yjc3Y1x1ZDFhNCBcdWQ2YzhcdWI4MjhcdWM3NDAgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYywgXHViM2M0XHViODVjXHViOTdjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjYyBcdWIyZTRcdWM3NGMsIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI4NWMgXHViMmU0XHVjMmRjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzExYyBcdWIwNWRcdWIwOWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVkNmM4XHViODI4XHVkNTU4XHViYTc0XHVjMTFjIFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWQ0OGRcdWFjYmRcdWIzYzQgXHVhYzEwXHVjMGMxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVjNzc0XHViYmY4IFx1YzljMFx1YjA5OFx1YWMwNCBcdWIzYzRcdWMyZGNcdWI5N2MgXHViMmU0XHVjMmRjIFx1YzljMFx1YjA5OFx1YWMwMFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWM5YzBcdWIwOWMgXHViM2M0XHViODVjXHViM2M0IFx1YjJlNFx1YzJkYyBcdWM5YzBcdWIwOThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNmM4XHViODI4XHVjNzQ0IFx1YzJkY1x1Yzc5MSBcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHViMjk0IFx1YzViNFx1YjI5MFx1YWNmM1x1Yzc3NCBcdWI0MThcdWM1YjRcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHVhY2UwLCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0YTRcdWM1ZDBcdWMxMWMgXHViMmVjXHViOWFjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHViMmVjXHViOWFjXHViMjk0IFx1YWM4M1x1YmNmNFx1YjJlNCBcdWIzNTQgXHVkM2I4XHVkNTU4XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YzU1ZVx1YzVkMFx1YzExYyBcdWIyZWNcdWI5YWNcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YmMxNFx1Yjc4Y1x1Yzc0NCBcdWI5YzlcdWM1NDRcdWM4ZmNcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHVjMmRjXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWI1NGMgXHViOWM4XHViMmU0IFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmMwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWMxMWNcdWI4NWMgXHVkNmM4XHViODI4XHVkNTVjIFx1YzU5MVx1Yzc3NCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM5ZGRcdWMyMTggXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM5YzBcdWIwOThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YWNiZFx1YzdjMVx1Yzc5MCBcdWMwYzFcdWIzNTVcdWM3NzRcdWM2NDAgXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM1YzZcdWM1NjBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDNlY1x1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM3N2NcdWJkODBcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDNlY1x1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZWRcdWQzMGNcdWMyZGNcdWQwYTRcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNTkxXHVjMjE4KSBcdWI2MTAsIFx1ZDNlY1x1YzdhNVx1YjQxYyBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzJkY1x1YzY0MCBcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVkNmM4XHViODI4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1YWM4Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDNlZFx1ZDMwYyBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMSwwMDAsIE4tMSAmbGU7IE0gJmxlOyA1LDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IEEsIEIsIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgQyAmbGU7IDEwLDAwMCkgQVx1YzY0MCBCXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWJhNzAsIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gQ1x1YWMwMCAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWQzZWNcdWM3YTVcdWI0MWMgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LiBcdWQzZWNcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IENcdWFjMTJcdWM3NzQgXHVjNTkxXHVjMjE4XHVjNzc0XHViYTcwLCBcdWM3NzQgXHVhYzEyXHVjNzQwIFx1YWRmOCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlNDRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIDEwXHVhYzFjIFx1YjNjNFx1Yjg1Y1x1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1ZDU1YyBcdWIzYzRcdWMyZGMgXHVjMzBkXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWQ2YzhcdWI4MjggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNWM2XHVjNTYwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQzZWRcdWQzMGMgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGF2ZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyODJweDsgd2lkdGg6MzM0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWQ3NVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkM2VjXHVjN2E1XHViNDFjIFx1YjNjNFx1Yjg1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wYXZlMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNThweDsgd2lkdGg6OTA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWQ2YzhcdWI4MjggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MSBcdWMyZGNcdWQwYTRcdWIyOTQgXHVhY2JkXHViODVjXHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViMmU0XHVjMTJmIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViM2M0XHViODVjIDEtMywgMy01LCAyLTVcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE4XHViMmU0XHViYTc0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDZjOFx1YjgyOFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjZDFkIFx1ZDNlZFx1ZDMwYyBcdWJlNDRcdWM2YTlcdWM3NDAgNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViODVjIDItNFx1YzY0MCAyLTVcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVjZjFjXHViM2M0IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNkMWQgXHVkM2VkXHVkMzBjIFx1YmU0NFx1YzZhOVx1Yzc3NCA2XHVjNzc0IFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0NzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUUkFJTklORyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFNsYXZrbyBhcmUgdHJhaW5pbmcgaGFyZCBmb3IgdGhlIGFubnVhbCB0YW5kZW0gY3ljbGluZyBtYXJhdGhvbiB0YWtpbmcgcGxhY2UgaW4gQ3JvYXRpYS4gVGhleSBuZWVkIHRvIGNob29zZSBhIHJvdXRlIHRvIHRyYWluIG9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgTiBjaXRpZXMgYW5kIE0gcm9hZHMgaW4gdGhlaXIgY291bnRyeS4gRXZlcnkgcm9hZCBjb25uZWN0cyB0d28gY2l0aWVzIGFuZCBjYW4gYmUgdHJhdmVyc2VkIGluIGJvdGggZGlyZWN0aW9ucy4gRXhhY3RseSBOJm1pbnVzOzEgb2YgdGhvc2Ugcm9hZHMgYXJlIHBhdmVkLCB3aGlsZSB0aGUgcmVzdCBvZiB0aGUgcm9hZHMgYXJlIHVucGF2ZWQgdHJhaWxzLiBGb3J0dW5hdGVseSwgdGhlIG5ldHdvcmsgb2Ygcm9hZHMgd2FzIGRlc2lnbmVkIHNvIHRoYXQgZWFjaCBwYWlyIG9mIGNpdGllcyBpcyBjb25uZWN0ZWQgYnkgYSBwYXRoIGNvbnNpc3Rpbmcgb2YgcGF2ZWQgcm9hZHMuIEluIG90aGVyIHdvcmRzLCB0aGUgTiBjaXRpZXMgYW5kIHRoZSBOJm1pbnVzOzEgcGF2ZWQgcm9hZHMgZm9ybSBhIHRyZWUgc3RydWN0dXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZGRpdGlvbmFsbHksIGVhY2ggY2l0eSBpcyBhbiBlbmRwb2ludCBmb3IgYXQgbW9zdCAxMCByb2FkcyB0b3RhbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSB0cmFpbmluZyByb3V0ZSBzdGFydHMgaW4gc29tZSBjaXR5LCBmb2xsb3dzIHNvbWUgcm9hZHMgYW5kIGVuZHMgaW4gdGhlIHNhbWUgY2l0eSBpdCBzdGFydGVkIGluLiBNaXJrbyBhbmQgU2xhdmtvIGxpa2UgdG8gc2VlIG5ldyBwbGFjZXMsIHNvIHRoZXkgbWFkZSBhIHJ1bGUgbmV2ZXIgdG8gZ28gdGhyb3VnaCB0aGUgc2FtZSBjaXR5IG5vciB0cmF2ZWwgdGhlIHNhbWUgcm9hZCB0d2ljZS4gVGhlIHRyYWluaW5nIHJvdXRlIG1heSBzdGFydCBpbiBhbnkgY2l0eSBhbmQgZG9lcyBub3QgbmVlZCB0byB2aXNpdCBldmVyeSBjaXR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5SaWRpbmcgaW4gdGhlIGJhY2sgc2VhdCBpcyBlYXNpZXIsIHNpbmNlIHRoZSByaWRlciBpcyBzaGllbGRlZCBmcm9tIHRoZSB3aW5kIGJ5IHRoZSByaWRlciBpbiB0aGUgZnJvbnQuIEJlY2F1c2Ugb2YgdGhpcywgTWlya28gYW5kIFNsYXZrbyBjaGFuZ2Ugc2VhdHMgaW4gZXZlcnkgY2l0eS4gVG8gZW5zdXJlIHRoYXQgdGhleSBnZXQgdGhlIHNhbWUgYW1vdW50IG9mIHRyYWluaW5nLCB0aGV5IG11c3QgY2hvb3NlIGEgcm91dGUgd2l0aCBhbiBldmVuIG51bWJlciBvZiByb2Fkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gYW5kIFNsYXZrbyYjMzk7cyBjb21wZXRpdG9ycyBkZWNpZGVkIHRvIGJsb2NrIHNvbWUgb2YgdGhlIHVucGF2ZWQgcm9hZHMsIG1ha2luZyBpdCBpbXBvc3NpYmxlIGZvciB0aGVtIHRvIGZpbmQgYSB0cmFpbmluZyByb3V0ZSBzYXRpc2Z5aW5nIHRoZSBhYm92ZSByZXF1aXJlbWVudHMuIEZvciBlYWNoIHVucGF2ZWQgcm9hZCB0aGVyZSBpcyBhIGNvc3QgKGEgcG9zaXRpdmUgaW50ZWdlcikgYXNzb2NpYXRlZCB3aXRoIGJsb2NraW5nIHRoZSByb2FkLiBJdCBpcyBpbXBvc3NpYmxlIHRvIGJsb2NrIHBhdmVkIHJvYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBuZXR3b3JrIG9mIGNpdGllcyBhbmQgcm9hZHMsIGZpbmRzIHRoZSBzbWFsbGVzdCB0b3RhbCBjb3N0IG5lZWRlZCB0byBibG9jayB0aGUgcm9hZHMgc28gdGhhdCBubyB0cmFpbmluZyByb3V0ZSBleGlzdHMgc2F0aXNmeWluZyB0aGUgYWJvdmUgcmVxdWlyZW1lbnRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDIgJmxlOyBOICZsZTsgMSAwMDAsIE4mbWludXM7MSAmbGU7IE0gJmxlOyA1IDAwMCksIHRoZSBudW1iZXIgb2YgY2l0aWVzIGFuZCB0aGUgdG90YWwgbnVtYmVyIG9mIHJvYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBBLCBCIGFuZCBDICgxICZsZTsgQSAmbGU7IE4sIDEgJmxlOyBCICZsZTsgTiwgMCAmbGU7IEMgJmxlOyAxMCAwMDApLCBkZXNjcmliaW5nIG9uZSByb2FkLiBUaGUgbnVtYmVycyBBIGFuZCBCIGFyZSBkaWZmZXJlbnQgYW5kIHRoZXkgcmVwcmVzZW50IHRoZSBjaXRpZXMgZGlyZWN0bHkgY29ubmVjdGVkIGJ5IHRoZSByb2FkLiBJZiBDPTAsIHRoZSByb2FkIGlzIHBhdmVkOyBvdGhlcndpc2UsIHRoZSByb2FkIGlzIHVucGF2ZWQgYW5kIEMgcmVwcmVzZW50cyB0aGUgY29zdCBvZiBibG9ja2luZyBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjaXR5IGlzIGFuIGVuZHBvaW50IGZvciBhdCBtb3N0IDEwIHJvYWRzLiBUaGVyZSB3aWxsIG5ldmVyIGJlIG1vcmUgdGhhbiBvbmUgcm9hZCBkaXJlY3RseSBjb25uZWN0aW5nIGEgc2luZ2xlIHBhaXIgb2YgY2l0aWVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgc21hbGxlc3QgdG90YWwgY29zdCBhcyBkZXNjcmliZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhdmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjgycHg7IG9wYWNpdHk6MC45OyB3aWR0aDozMzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGF5b3V0IG9mIHRoZSByb2FkcyBhbmQgY2l0aWVzIGluIHRoZSBmaXJzdCBleGFtcGxlLiBQYXZlZCByb2FkcyBhcmUgc2hvd24gaW4gYm9sZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wYXZlMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNThweDsgd2lkdGg6OTA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIGZpdmUgcG9zc2libGUgcm91dGVzIGZvciBNaXJrbyBhbmQgU2xhdmtvLiBJZiB0aGUgcm9hZHMgMS0zLCAzLTUgYW5kIDItNSBhcmUgYmxvY2tlZCwgdGhlbiBNaXJrbyBhbmQgU2xhdmtvIGNhbm5vdCB1c2UgYW55IG9mIHRoZSBmaXZlIHJvdXRlcy4gVGhlIGNvc3Qgb2YgYmxvY2tpbmcgdGhlc2UgdGhyZWUgcm9hZHMgaXMgNS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SXQgaXMgYWxzbyBwb3NzaWJsZSB0byBibG9jayBqdXN0IHR3byByb2FkcywgMi00IGFuZCAyLTUsIGJ1dCB0aGlzIHdvdWxkIHJlc3VsdCBpbiBhIGhpZ2hlciBjb3N0IG9mIDYuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2007 6번