시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB276786132.620%

문제

양항승 왕국은 거의 모든 지역이 강과 숲으로 이루어져 있다. 상류의 작은 강들은 모여서 큰 강이 되며, 그 강도 다른 강과 만나 더 커져 나중에는 하류로 가면 거대한 강 하나만이 남아 양항승 왕국 근처의 바다로 흘러간다.

양항승 왕국에는 나무꾼들이 사는 n개의 마을이 강변에 있다. 그런데 현재는 목공소가 강의 최하류인 양항승 왕국에 하나만 있기 때문에, 제각기 사는 곳에서 나무를 벤 나무꾼들은 통나무를 강에다 띄워서 그 목공소로 보낸다. 그래서 항승이는  통나무를 하류로 흘려보내는 물류비용을 줄이기 위해, 마을들 중 적당한 곳에 k개의 목공소를 더 짓기로 했다. 목공소가 더 생기면, 상류에서 흘러보낸 통나무들은 왕국까지 갈 필요 없이 처음으로 거치는 목공소에서 바로 처리를 할 수 있으며, 목공소가 있는 마을에서 생산된 통나무는 강을 거칠 필요조차 없어진다.

목공소를 세울 곳을 결정하기 위해, 왕의 신하들은 각 마을별로 연간 생산되는 통나무의 양을 조사해 두었다. 강물은 하류로 갈수록 합쳐지기만 하지 갈라지지는 않기 때문에, 각 마을에서 왕국까지 가는 경로는 오직 하나만 존재한다. 마을별로 강을 이용해 이웃 마을이나 현재의 최종 목적지인 왕국까지 가는 거리에 대한 자료 역시 있다. 이것을 토대로, 전국의 나무의 물류비용을 최소화하려면 어디에 목공소를 건설하면 좋을지 결정하는 프로그램을 작성하시오. 통나무 하나를 강으로 1km 거리만치 운반하는데 드는 비용은 1로 한다. 예를 들어 통나무 2개를 5km 운반하는데 드는 비용을 계산하면 2*5=10 이다.

입력

첫 줄에는 왕국을 제외한 마을의 수 n과 추가로 지으려고 하는 목공소의 수 k가 있다. (2≤n≤100, 1≤k≤50이고 k≤n) 마을들은 1부터 n까지 번호가 부여되어 있으며, 왕국의 번호는 0이다. 그 다음 각 n개의 각 줄마다 다음의 3개의 정수가 주어진다.

  • wi─마을 i에서 생산하는 나무의 개수
  • vi─마을 i에서 하류쪽으로 가면 나오는 첫 번째 마을(혹은 왕국 본토)
  • di─마을 i에서 마을 vi까지의 거리

총 운반비는 2000000000을 넘지 않는다.

출력

목공소를 최적의 위치에다 지었을 때, 마을 전역에서 생산되는 통나무를 "적당한 목공소가 있는 곳"까지 강으로 운반하는데 드는 총 비용의 최솟값을 출력한다.

예제 입력 1

4 2
1 0 1
1 1 10
10 2 5
1 2 3

예제 출력 1

4

힌트

위의 그림에서 선분은 강을 뜻하고, 원으로 된 정점은 마을을 뜻한다. 선분 위의 숫자는 해당 구간의 거리이며, 원 안의 숫자는 마을 번호, 그리고 원 아래의 숫자는 그 마을에서 매년 생산되는 통나무의 수이다.

이 예제에서 목공소를 지어야 하는 최적의 위치 두 곳은 2번과 3번 마을이다. 이 경우 4번 마을의 통나무를 2번 마을로 보내는 비용 1×3과, 1번 마을의 통나무를 양항승 왕국으로 보내는 비용 1×1만이 필요하다.

W3sicHJvYmxlbV9pZCI6IjE4MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzRcdWMyMThcdWMxYTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1ZDU2ZFx1YzJiOSBcdWM2NTVcdWFkNmRcdWM3NDAgXHVhYzcwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM5YzBcdWM1ZWRcdWM3NzQgXHVhYzE1XHVhY2ZjIFx1YzIzMlx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMwYzFcdWI5NThcdWM3NTggXHVjNzkxXHVjNzQwIFx1YWMxNVx1YjRlNFx1Yzc0MCBcdWJhYThcdWM1ZWNcdWMxMWMgXHVkMDcwIFx1YWMxNVx1Yzc3NCBcdWI0MThcdWJhNzAsIFx1YWRmOCBcdWFjMTVcdWIzYzQgXHViMmU0XHViOTc4IFx1YWMxNVx1YWNmYyBcdWI5Y2NcdWIwOTggXHViMzU0IFx1Y2VlNFx1YzgzOCBcdWIwOThcdWM5MTFcdWM1ZDBcdWIyOTQgXHVkNTU4XHViOTU4XHViODVjIFx1YWMwMFx1YmE3NCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHVhYzE1IFx1ZDU1OFx1YjA5OFx1YjljY1x1Yzc3NCBcdWIwYThcdWM1NDQgXHVjNTkxXHVkNTZkXHVjMmI5IFx1YzY1NVx1YWQ2ZCBcdWFkZmNcdWNjOThcdWM3NTggXHViYzE0XHViMmU0XHViODVjIFx1ZDc1OFx1YjdlY1x1YWMwNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTkxXHVkNTZkXHVjMmI5IFx1YzY1NVx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzRcdWFmYmNcdWI0ZTRcdWM3NzQgXHVjMGFjXHViMjk0IG5cdWFjMWNcdWM3NTggXHViOWM4XHVjNzQ0XHVjNzc0IFx1YWMxNVx1YmNjMFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWQ2MDRcdWM3YWNcdWIyOTQgXHViYWE5XHVhY2Y1XHVjMThjXHVhYzAwIFx1YWMxNVx1Yzc1OCBcdWNkNWNcdWQ1NThcdWI5NThcdWM3NzggXHVjNTkxXHVkNTZkXHVjMmI5IFx1YzY1NVx1YWQ2ZFx1YzVkMCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjODFjXHVhYzAxXHVhZTMwIFx1YzBhY1x1YjI5NCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHViMDk4XHViYjM0XHViOTdjIFx1YmNhNCBcdWIwOThcdWJiMzRcdWFmYmNcdWI0ZTRcdWM3NDAgXHVkMWI1XHViMDk4XHViYjM0XHViOTdjIFx1YWMxNVx1YzVkMFx1YjJlNCBcdWI3NDRcdWM2Y2NcdWMxMWMgXHVhZGY4IFx1YmFhOVx1YWNmNVx1YzE4Y1x1Yjg1YyBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgJm5ic3A7XHVkMWI1XHViMDk4XHViYjM0XHViOTdjIFx1ZDU1OFx1Yjk1OFx1Yjg1YyBcdWQ3NThcdWI4MjRcdWJjZjRcdWIwYjRcdWIyOTQgXHViYjNjXHViOTU4XHViZTQ0XHVjNmE5XHVjNzQ0IFx1YzkwNFx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YjljOFx1Yzc0NFx1YjRlNCBcdWM5MTEgXHVjODAxXHViMmY5XHVkNTVjIFx1YWNmM1x1YzVkMCBrXHVhYzFjXHVjNzU4IFx1YmFhOVx1YWNmNVx1YzE4Y1x1Yjk3YyBcdWIzNTQgXHVjOWQzXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHViYWE5XHVhY2Y1XHVjMThjXHVhYzAwIFx1YjM1NCBcdWMwZGRcdWFlMzBcdWJhNzQsIFx1YzBjMVx1Yjk1OFx1YzVkMFx1YzExYyBcdWQ3NThcdWI3ZWNcdWJjZjRcdWIwYjggXHVkMWI1XHViMDk4XHViYjM0XHViNGU0XHVjNzQwIFx1YzY1NVx1YWQ2ZFx1YWU0Y1x1YzljMCBcdWFjMDggXHVkNTQ0XHVjNjk0IFx1YzVjNlx1Yzc3NCBcdWNjOThcdWM3NGNcdWM3M2NcdWI4NWMgXHVhYzcwXHVjZTU4XHViMjk0IFx1YmFhOVx1YWNmNVx1YzE4Y1x1YzVkMFx1YzExYyBcdWJjMTRcdWI4NWMgXHVjYzk4XHViOWFjXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJhYTlcdWFjZjVcdWMxOGNcdWFjMDAgXHVjNzg4XHViMjk0IFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyBcdWMwZGRcdWMwYjBcdWI0MWMgXHVkMWI1XHViMDk4XHViYjM0XHViMjk0IFx1YWMxNVx1Yzc0NCBcdWFjNzBcdWNlNjAgXHVkNTQ0XHVjNjk0XHVjODcwXHVjYzI4IFx1YzVjNlx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE5XHVhY2Y1XHVjMThjXHViOTdjIFx1YzEzOFx1YzZiOCBcdWFjZjNcdWM3NDQgXHVhY2IwXHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjNjU1XHVjNzU4IFx1YzJlMFx1ZDU1OFx1YjRlNFx1Yzc0MCBcdWFjMDEgXHViOWM4XHVjNzQ0XHViY2M0XHViODVjIFx1YzVmMFx1YWMwNCBcdWMwZGRcdWMwYjBcdWI0MThcdWIyOTQgXHVkMWI1XHViMDk4XHViYjM0XHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWM4NzBcdWMwYWNcdWQ1NzQgXHViNDUwXHVjNWM4XHViMmU0LiBcdWFjMTVcdWJiM2NcdWM3NDAgXHVkNTU4XHViOTU4XHViODVjIFx1YWMwOFx1YzIxOFx1Yjg1ZCBcdWQ1NjlcdWNjZDBcdWM5YzBcdWFlMzBcdWI5Y2MgXHVkNTU4XHVjOWMwIFx1YWMwOFx1Yjc3Y1x1YzljMFx1YzljMFx1YjI5NCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjMDEgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzY1NVx1YWQ2ZFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViMjk0IFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWI5YzhcdWM3NDRcdWJjYzRcdWI4NWMgXHVhYzE1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM3NzRcdWM2YzMgXHViOWM4XHVjNzQ0XHVjNzc0XHViMDk4IFx1ZDYwNFx1YzdhY1x1Yzc1OCBcdWNkNWNcdWM4ODUgXHViYWE5XHVjODAxXHVjOWMwXHVjNzc4IFx1YzY1NVx1YWQ2ZFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhYzcwXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3OTBcdWI4Y2MgXHVjNWVkXHVjMmRjIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFx1ZDFhMFx1YjMwMFx1Yjg1YywgXHVjODA0XHVhZDZkXHVjNzU4IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWJiM2NcdWI5NThcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViODI0XHViYTc0IFx1YzViNFx1YjUxNFx1YzVkMCBcdWJhYTlcdWFjZjVcdWMxOGNcdWI5N2MgXHVhYzc0XHVjMTI0XHVkNTU4XHViYTc0IFx1Yzg4Ylx1Yzc0NFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkMWI1XHViMDk4XHViYjM0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjMTVcdWM3M2NcdWI4NWMgMWttIFx1YWM3MFx1YjlhY1x1YjljY1x1Y2U1OCBcdWM2YjRcdWJjMThcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCAxXHViODVjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWQxYjVcdWIwOThcdWJiMzQgMlx1YWMxY1x1Yjk3YyA1a20gXHVjNmI0XHViYzE4XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHViYTc0IDIqNT0xMCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzY1NVx1YWQ2ZFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1Y2Q5NFx1YWMwMFx1Yjg1YyBcdWM5YzBcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmFhOVx1YWNmNVx1YzE4Y1x1Yzc1OCBcdWMyMTgga1x1YWMwMCBcdWM3ODhcdWIyZTQuICgyJmxlO24mbGU7MTAwLCAxJmxlO2smbGU7NTBcdWM3NzRcdWFjZTAgayZsZTtuKSBcdWI5YzhcdWM3NDRcdWI0ZTRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkODBcdWM1ZWNcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM2NTVcdWFkNmRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDBcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVhYzAxIG5cdWFjMWNcdWM3NTggXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBcdWIyZTRcdWM3NGNcdWM3NTggM1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnc8c3ViPmk8XC9zdWI+XHUyNTAwXHViOWM4XHVjNzQ0IGlcdWM1ZDBcdWMxMWMgXHVjMGRkXHVjMGIwXHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHQ8bGk+djxzdWI+aTxcL3N1Yj5cdTI1MDBcdWI5YzhcdWM3NDQgaVx1YzVkMFx1YzExYyBcdWQ1NThcdWI5NThcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzAwXHViYTc0IFx1YjA5OFx1YzYyNFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjljOFx1Yzc0NChcdWQ2MzlcdWM3NDAgXHVjNjU1XHVhZDZkIFx1YmNmOFx1ZDFhMCk8XC9saT5cclxuXHQ8bGk+ZDxzdWI+aTxcL3N1Yj5cdTI1MDBcdWI5YzhcdWM3NDQgaVx1YzVkMFx1YzExYyBcdWI5YzhcdWM3NDQgdjxzdWI+aTxcL3N1Yj5cdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjZDFkIFx1YzZiNFx1YmMxOFx1YmU0NFx1YjI5NCAyMDAwMDAwMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE5XHVhY2Y1XHVjMThjXHViOTdjIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDBcdWIyZTQgXHVjOWMwXHVjNWM4XHVjNzQ0IFx1YjU0YywgXHViOWM4XHVjNzQ0IFx1YzgwNFx1YzVlZFx1YzVkMFx1YzExYyBcdWMwZGRcdWMwYjBcdWI0MThcdWIyOTQgXHVkMWI1XHViMDk4XHViYjM0XHViOTdjICZxdW90O1x1YzgwMVx1YjJmOVx1ZDU1YyBcdWJhYTlcdWFjZjVcdWMxOGNcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNmMyZxdW90O1x1YWU0Y1x1YzljMCBcdWFjMTVcdWM3M2NcdWI4NWMgXHVjNmI0XHViYzE4XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWNkMWQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3RlbXAxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3N3B4OyB3aWR0aDoyNzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWFjMTVcdWM3NDQgXHViNzNiXHVkNTU4XHVhY2UwLCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHViNDFjIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWI5YzhcdWM3NDRcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LiBcdWMxMjBcdWJkODQgXHVjNzA0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc3NFx1YmE3MCwgXHVjNmQwIFx1YzU0OFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViOWM4XHVjNzQ0IFx1YmM4OFx1ZDYzOCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzZkMCBcdWM1NDRcdWI3OThcdWM3NTggXHVjMjJiXHVjNzkwXHViMjk0IFx1YWRmOCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHViOWU0XHViMTQ0IFx1YzBkZFx1YzBiMFx1YjQxOFx1YjI5NCBcdWQxYjVcdWIwOThcdWJiMzRcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YmFhOVx1YWNmNVx1YzE4Y1x1Yjk3YyBcdWM5YzBcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWM3MDRcdWNlNTggXHViNDUwIFx1YWNmM1x1Yzc0MCAyXHViYzg4XHVhY2ZjIDNcdWJjODggXHViOWM4XHVjNzQ0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwIDRcdWJjODggXHViOWM4XHVjNzQ0XHVjNzU4IFx1ZDFiNVx1YjA5OFx1YmIzNFx1Yjk3YyAyXHViYzg4IFx1YjljOFx1Yzc0NFx1Yjg1YyBcdWJjZjRcdWIwYjRcdWIyOTQgXHViZTQ0XHVjNmE5IDEmdGltZXM7M1x1YWNmYywgMVx1YmM4OCBcdWI5YzhcdWM3NDRcdWM3NTggXHVkMWI1XHViMDk4XHViYjM0XHViOTdjIFx1YzU5MVx1ZDU2ZFx1YzJiOSBcdWM2NTVcdWFkNmRcdWM3M2NcdWI4NWMgXHViY2Y0XHViMGI0XHViMjk0IFx1YmU0NFx1YzZhOSAxJnRpbWVzOzFcdWI5Y2NcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTgwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJpdmVycyIsImRlc2NyaXB0aW9uIjoiPHA+TmVhcmx5IGFsbCBvZiB0aGUgS2luZ2RvbSBvZiBCeXRlbGFuZCBpcyBjb3ZlcmVkIGJ5IGZvcmVzdHMgYW5kIHJpdmVycy4gU21hbGwgcml2ZXJzIG1lZXQgdG8gZm9ybSBiaWdnZXIgcml2ZXJzLCB3aGljaCBhbHNvIG1lZXQgYW5kLCBpbiB0aGUgZW5kLCBhbGwgdGhlIHJpdmVycyBcdWZiMDJvdyB0b2dldGhlciBpbnRvIG9uZSBiaWcgcml2ZXIuIFRoZSBiaWcgcml2ZXIgbWVldHMgdGhlIHNlYSBuZWFyIEJ5dGV0b3duLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgbiBsdW1iZXJqYWNrcyZyc3F1bzsgdmlsbGFnZXMgaW4gQnl0ZWxhbmQsIGVhY2ggcGxhY2VkIG5lYXIgYSByaXZlci4gQ3VycmVudGx5LCB0aGVyZSBpcyBhIGJpZyBzYXdtaWxsIGluIEJ5dGV0b3duIHRoYXQgcHJvY2Vzc2VzIGFsbCB0cmVlcyBjdXQgaW4gdGhlIEtpbmdkb20uIFRoZSB0cmVlcyBcdWZiMDJvYXQgZnJvbSB0aGUgdmlsbGFnZXMgZG93biB0aGUgcml2ZXJzIHRvIHRoZSBzYXdtaWxsIGluIEJ5dGV0b3duLiBUaGUga2luZyBvZiBCeXRlbGFuZCBkZWNpZGVkIHRvIGJ1aWxkIGsgYWRkaXRpb25hbCBzYXdtaWxscyBpbiB2aWxsYWdlcyB0byByZWR1Y2UgdGhlIGNvc3Qgb2YgdHJhbnNwb3J0aW5nIHRoZSB0cmVlcyBkb3ducml2ZXIuIEFmdGVyIGJ1aWxkaW5nIHRoZSBzYXdtaWxscywgdGhlIHRyZWVzIG5lZWQgbm90IFx1ZmIwMm9hdCB0byBCeXRldG93biwgYnV0IGNhbiBiZSBwcm9jZXNzZWQgaW4gdGhlIFx1ZmIwMXJzdCBzYXdtaWxsIHRoZXkgZW5jb3VudGVyIGRvd25yaXZlci4gT2J2aW91c2x5LCB0aGUgdHJlZXMgY3V0IG5lYXIgYSB2aWxsYWdlIHdpdGggYSBzYXdtaWxsIG5lZWQgbm90IGJlIHRyYW5zcG9ydGVkIGJ5IHJpdmVyLiBJdCBzaG91bGQgYmUgbm90ZWQgdGhhdCB0aGUgcml2ZXJzIGluIEJ5dGVsYW5kIGRvIG5vdCBmb3JrLiBUaGVyZWZvcmUsIGZvciBlYWNoIHZpbGxhZ2UsIHRoZXJlIGlzIGEgdW5pcXVlIHdheSBkb3ducml2ZXIgZnJvbSB0aGUgdmlsbGFnZSB0byBCeXRldG93bi48XC9wPlxyXG5cclxuPHA+VGhlIGtpbmcmcnNxdW87cyBhY2NvdW50YW50cyBjYWxjdWxhdGVkIGhvdyBtYW55IHRyZWVzIGFyZSBjdXQgYnkgZWFjaCB2aWxsYWdlIHBlciB5ZWFyLiBZb3UgbXVzdCBkZWNpZGUgd2hlcmUgdG8gYnVpbGQgdGhlIHNhd21pbGxzIHRvIG1pbmltaXplIHRoZSB0b3RhbCBjb3N0IG9mIHRyYW5zcG9ydGluZyB0aGUgdHJlZXMgcGVyIHllYXIuIFJpdmVyIHRyYW5zcG9ydGF0aW9uIGNvc3RzIG9uZSBjZW50IHBlciBraWxvbWV0cmUsIHBlciB0cmVlLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgbnVtYmVyIG9mIHZpbGxhZ2VzLCB0aGUgbnVtYmVyIG9mIGFkZGl0aW9uYWwgc2F3bWlsbHMgdG8gYmUgYnVpbHQsIHRoZSBudW1iZXIgb2YgdHJlZXMgY3V0IG5lYXIgZWFjaCB2aWxsYWdlLCBhbmQgZGVzY3JpcHRpb25zIG9mIHRoZSByaXZlcnMsPFwvbGk+XHJcblx0PGxpPmNhbGN1bGF0ZXMgdGhlIG1pbmltYWwgY29zdCBvZiByaXZlciB0cmFuc3BvcnRhdGlvbiBhZnRlciBidWlsZGluZyBhZGRpdGlvbmFsIHNhd21pbGxzLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzOiBuICZtZGFzaDsgdGhlIG51bWJlciBvZiB2aWxsYWdlcyBvdGhlciB0aGFuIEJ5dGV0b3duICgyICZsZTsgbiAmbGU7IDEwMCksIGFuZCBrICZtZGFzaDsgdGhlIG51bWJlciBvZiBhZGRpdGlvbmFsIHNhd21pbGxzIHRvIGJlIGJ1aWx0ICgxICZsZTsgayAmbGU7IDUwIGFuZCBrICZsZTsgbikuIFRoZSB2aWxsYWdlcyBhcmUgbnVtYmVyZWQgMSwyLC4uLixuLCB3aGlsZSBCeXRldG93biBoYXMgbnVtYmVyIDAuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gTGluZSBpKzEgY29udGFpbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dzxzdWI+aTxcL3N1Yj4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHRyZWVzIGN1dCBuZWFyIHZpbGxhZ2UgaSBwZXIgeWVhciAoMCAmbGU7IHc8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDApLDxcL2xpPlxyXG5cdDxsaT52PHN1Yj5pPFwvc3ViPiAmbWRhc2g7IHRoZSBcdWZiMDFyc3QgdmlsbGFnZSAob3IgQnl0ZXRvd24pIGRvd25yaXZlciBmcm9tIHZpbGxhZ2UgaSAoMCAmbGU7IHY8c3ViPmk8XC9zdWI+ICZsZTsgbiksPFwvbGk+XHJcblx0PGxpPmQ8c3ViPmk8XC9zdWI+ICZtZGFzaDsgdGhlIGRpc3RhbmNlIChpbiBraWxvbWV0cmVzKSBieSByaXZlciBmcm9tIHZpbGxhZ2UgaSB0byB2PHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDApLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgdG90YWwgY29zdCBvZiBcdWZiMDJvYXRpbmcgYWxsIHRoZSB0cmVlcyB0byB0aGUgc2F3bWlsbCBpbiBCeXRldG93biBpbiBvbmUgeWVhciBkb2VzIG5vdCBleGNlZWQgMjAwMDAwMDAwMCBjZW50cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlcjogdGhlIG1pbmltYWwgY29zdCBvZiByaXZlciB0cmFuc3BvcnRhdGlvbiAoaW4gY2VudHMpLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Jpdi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTdweDsgd2lkdGg6MjU3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGFib3ZlIHBpY3R1cmUgaWxsdXN0cmF0ZXMgdGhlIGV4YW1wbGUgaW5wdXQgZGF0YS4gVmlsbGFnZSBudW1iZXJzIGFyZSBnaXZlbiBpbnNpZGUgY2lyY2xlcy4gTnVtYmVycyBiZWxvdyB0aGUgY2lyY2xlcyByZXByZXNlbnRzIHRoZSBudW1iZXIgb2YgdHJlZXMgY3V0IG5lYXIgdmlsbGFnZXMuIE51bWJlcnMgYWJvdmUgdGhlIGFycm93cyByZXByZXNlbnQgcml2ZXJzJnJzcXVvOyBsZW5ndGhzLjxcL3A+XHJcblxyXG48cD5UaGUgc2F3bWlsbHMgc2hvdWxkIGJlIGJ1aWx0IGluIHZpbGxhZ2VzIDIgYW5kIDMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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