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

문제

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

두 사람이 살고있는 나라에는 도시가 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YWNiZFx1YzdjMVx1Yzc5MCBcdWMwYzFcdWIzNTVcdWM3NzRcdWM2NDAgXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM1YzZcdWM1NjBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDNlY1x1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM3N2NcdWJkODBcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDNlY1x1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZWRcdWQzMGNcdWMyZGNcdWQwYTRcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNTkxXHVjMjE4KSBcdWI2MTAsIFx1ZDNlY1x1YzdhNVx1YjQxYyBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzJkY1x1YzY0MCBcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVkNmM4XHViODI4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1YWM4Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDNlZFx1ZDMwYyBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMSwwMDAsIE4tMSAmbGU7IE0gJmxlOyA1LDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IEEsIEIsIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgQyAmbGU7IDEwLDAwMCkgQVx1YzY0MCBCXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWJhNzAsIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gQ1x1YWMwMCAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWQzZWNcdWM3YTVcdWI0MWMgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LiBcdWQzZWNcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IENcdWFjMTJcdWM3NzQgXHVjNTkxXHVjMjE4XHVjNzc0XHViYTcwLCBcdWM3NzQgXHVhYzEyXHVjNzQwIFx1YWRmOCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlNDRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIDEwXHVhYzFjIFx1YjNjNFx1Yjg1Y1x1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1ZDU1YyBcdWIzYzRcdWMyZGMgXHVjMzBkXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWQ2YzhcdWI4MjggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNWM2XHVjNTYwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQzZWRcdWQzMGMgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGF2ZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyODJweDsgd2lkdGg6MzM0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWQ3NVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkM2VjXHVjN2E1XHViNDFjIFx1YjNjNFx1Yjg1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wYXZlMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNThweDsgd2lkdGg6OTA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWQ2YzhcdWI4MjggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MSBcdWMyZGNcdWQwYTRcdWIyOTQgXHVhY2JkXHViODVjXHViMjk0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViMmU0XHVjMTJmIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViM2M0XHViODVjIDEtMywgMy01LCAyLTVcdWI5N2MgXHVkM2VkXHVkMzBjXHVjMmRjXHVkMGE4XHViMmU0XHViYTc0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDZjOFx1YjgyOFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWNkMWQgXHVkM2VkXHVkMzBjIFx1YmU0NFx1YzZhOVx1Yzc0MCA1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWI4NWMgMi00XHVjNjQwIDItNVx1Yjk3YyBcdWQzZWRcdWQzMGNcdWMyZGNcdWNmMWNcdWIzYzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Y2QxZCBcdWQzZWRcdWQzMGMgXHViZTQ0XHVjNmE5XHVjNzc0IDZcdWM3NzQgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTQ3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRSQUlOSU5HIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSB0cmFpbmluZyBoYXJkIGZvciB0aGUgYW5udWFsIHRhbmRlbSBjeWNsaW5nIG1hcmF0aG9uIHRha2luZyBwbGFjZSBpbiBDcm9hdGlhLiBUaGV5IG5lZWQgdG8gY2hvb3NlIGEgcm91dGUgdG8gdHJhaW4gb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIGNpdGllcyBhbmQgTSByb2FkcyBpbiB0aGVpciBjb3VudHJ5LiBFdmVyeSByb2FkIGNvbm5lY3RzIHR3byBjaXRpZXMgYW5kIGNhbiBiZSB0cmF2ZXJzZWQgaW4gYm90aCBkaXJlY3Rpb25zLiBFeGFjdGx5IE4mbWludXM7MSBvZiB0aG9zZSByb2FkcyBhcmUgcGF2ZWQsIHdoaWxlIHRoZSByZXN0IG9mIHRoZSByb2FkcyBhcmUgdW5wYXZlZCB0cmFpbHMuIEZvcnR1bmF0ZWx5LCB0aGUgbmV0d29yayBvZiByb2FkcyB3YXMgZGVzaWduZWQgc28gdGhhdCBlYWNoIHBhaXIgb2YgY2l0aWVzIGlzIGNvbm5lY3RlZCBieSBhIHBhdGggY29uc2lzdGluZyBvZiBwYXZlZCByb2Fkcy4gSW4gb3RoZXIgd29yZHMsIHRoZSBOIGNpdGllcyBhbmQgdGhlIE4mbWludXM7MSBwYXZlZCByb2FkcyBmb3JtIGEgdHJlZSBzdHJ1Y3R1cmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFkZGl0aW9uYWxseSwgZWFjaCBjaXR5IGlzIGFuIGVuZHBvaW50IGZvciBhdCBtb3N0IDEwIHJvYWRzIHRvdGFsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHRyYWluaW5nIHJvdXRlIHN0YXJ0cyBpbiBzb21lIGNpdHksIGZvbGxvd3Mgc29tZSByb2FkcyBhbmQgZW5kcyBpbiB0aGUgc2FtZSBjaXR5IGl0IHN0YXJ0ZWQgaW4uIE1pcmtvIGFuZCBTbGF2a28gbGlrZSB0byBzZWUgbmV3IHBsYWNlcywgc28gdGhleSBtYWRlIGEgcnVsZSBuZXZlciB0byBnbyB0aHJvdWdoIHRoZSBzYW1lIGNpdHkgbm9yIHRyYXZlbCB0aGUgc2FtZSByb2FkIHR3aWNlLiBUaGUgdHJhaW5pbmcgcm91dGUgbWF5IHN0YXJ0IGluIGFueSBjaXR5IGFuZCBkb2VzIG5vdCBuZWVkIHRvIHZpc2l0IGV2ZXJ5IGNpdHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJpZGluZyBpbiB0aGUgYmFjayBzZWF0IGlzIGVhc2llciwgc2luY2UgdGhlIHJpZGVyIGlzIHNoaWVsZGVkIGZyb20gdGhlIHdpbmQgYnkgdGhlIHJpZGVyIGluIHRoZSBmcm9udC4gQmVjYXVzZSBvZiB0aGlzLCBNaXJrbyBhbmQgU2xhdmtvIGNoYW5nZSBzZWF0cyBpbiBldmVyeSBjaXR5LiBUbyBlbnN1cmUgdGhhdCB0aGV5IGdldCB0aGUgc2FtZSBhbW91bnQgb2YgdHJhaW5pbmcsIHRoZXkgbXVzdCBjaG9vc2UgYSByb3V0ZSB3aXRoIGFuIGV2ZW4gbnVtYmVyIG9mIHJvYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBhbmQgU2xhdmtvJiMzOTtzIGNvbXBldGl0b3JzIGRlY2lkZWQgdG8gYmxvY2sgc29tZSBvZiB0aGUgdW5wYXZlZCByb2FkcywgbWFraW5nIGl0IGltcG9zc2libGUgZm9yIHRoZW0gdG8gZmluZCBhIHRyYWluaW5nIHJvdXRlIHNhdGlzZnlpbmcgdGhlIGFib3ZlIHJlcXVpcmVtZW50cy4gRm9yIGVhY2ggdW5wYXZlZCByb2FkIHRoZXJlIGlzIGEgY29zdCAoYSBwb3NpdGl2ZSBpbnRlZ2VyKSBhc3NvY2lhdGVkIHdpdGggYmxvY2tpbmcgdGhlIHJvYWQuIEl0IGlzIGltcG9zc2libGUgdG8gYmxvY2sgcGF2ZWQgcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIG5ldHdvcmsgb2YgY2l0aWVzIGFuZCByb2FkcywgZmluZHMgdGhlIHNtYWxsZXN0IHRvdGFsIGNvc3QgbmVlZGVkIHRvIGJsb2NrIHRoZSByb2FkcyBzbyB0aGF0IG5vIHRyYWluaW5nIHJvdXRlIGV4aXN0cyBzYXRpc2Z5aW5nIHRoZSBhYm92ZSByZXF1aXJlbWVudHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMiAmbGU7IE4gJmxlOyAxIDAwMCwgTiZtaW51czsxICZsZTsgTSAmbGU7IDUgMDAwKSwgdGhlIG51bWJlciBvZiBjaXRpZXMgYW5kIHRoZSB0b3RhbCBudW1iZXIgb2Ygcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIgYW5kIEMgKDEgJmxlOyBBICZsZTsgTiwgMSAmbGU7IEIgJmxlOyBOLCAwICZsZTsgQyAmbGU7IDEwIDAwMCksIGRlc2NyaWJpbmcgb25lIHJvYWQuIFRoZSBudW1iZXJzIEEgYW5kIEIgYXJlIGRpZmZlcmVudCBhbmQgdGhleSByZXByZXNlbnQgdGhlIGNpdGllcyBkaXJlY3RseSBjb25uZWN0ZWQgYnkgdGhlIHJvYWQuIElmIEM9MCwgdGhlIHJvYWQgaXMgcGF2ZWQ7IG90aGVyd2lzZSwgdGhlIHJvYWQgaXMgdW5wYXZlZCBhbmQgQyByZXByZXNlbnRzIHRoZSBjb3N0IG9mIGJsb2NraW5nIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNpdHkgaXMgYW4gZW5kcG9pbnQgZm9yIGF0IG1vc3QgMTAgcm9hZHMuIFRoZXJlIHdpbGwgbmV2ZXIgYmUgbW9yZSB0aGFuIG9uZSByb2FkIGRpcmVjdGx5IGNvbm5lY3RpbmcgYSBzaW5nbGUgcGFpciBvZiBjaXRpZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGEgc2luZ2xlIGludGVnZXIsIHRoZSBzbWFsbGVzdCB0b3RhbCBjb3N0IGFzIGRlc2NyaWJlZCBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGF2ZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyODJweDsgb3BhY2l0eTowLjk7IHdpZHRoOjMzNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBsYXlvdXQgb2YgdGhlIHJvYWRzIGFuZCBjaXRpZXMgaW4gdGhlIGZpcnN0IGV4YW1wbGUuIFBhdmVkIHJvYWRzIGFyZSBzaG93biBpbiBib2xkLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhdmUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1OHB4OyB3aWR0aDo5MDVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgZml2ZSBwb3NzaWJsZSByb3V0ZXMgZm9yIE1pcmtvIGFuZCBTbGF2a28uIElmIHRoZSByb2FkcyAxLTMsIDMtNSBhbmQgMi01IGFyZSBibG9ja2VkLCB0aGVuIE1pcmtvIGFuZCBTbGF2a28gY2Fubm90IHVzZSBhbnkgb2YgdGhlIGZpdmUgcm91dGVzLiBUaGUgY29zdCBvZiBibG9ja2luZyB0aGVzZSB0aHJlZSByb2FkcyBpcyA1LiZuYnNwOzxcL3A+XHJcblxyXG48cD5JdCBpcyBhbHNvIHBvc3NpYmxlIHRvIGJsb2NrIGp1c3QgdHdvIHJvYWRzLCAyLTQgYW5kIDItNSwgYnV0IHRoaXMgd291bGQgcmVzdWx0IGluIGEgaGlnaGVyIGNvc3Qgb2YgNi48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2007 > Day 2 6번