시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 67 29 20 55.556%

문제

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

양항승 왕국에는 나무꾼들이 사는 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+aTxcL3N1Yj5cdTI1MDBcdWI5YzhcdWM3NDQgaVx1YzVkMFx1YzExYyBcdWQ1NThcdWI5NThcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzAwXHViYTc0IFx1YjA5OFx1YzYyNFx1YjI5NCBcdWNjYWJcdWJjODhcdWM5ZjggXHViOWM4XHVjNzQ0KFx1ZDYzOVx1Yzc0MCBcdWM2NTVcdWFkNmQgXHViY2Y4XHVkMWEwKTxcL2xpPlxyXG5cdDxsaT5kPHN1Yj5pPFwvc3ViPlx1MjUwMFx1YjljOFx1Yzc0NCBpXHVjNWQwXHVjMTFjIFx1YjljOFx1Yzc0NCB2PHN1Yj5pPFwvc3ViPlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWM8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWNkMWQgXHVjNmI0XHViYzE4XHViZTQ0XHViMjk0IDIwMDAwMDAwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJhYTlcdWFjZjVcdWMxOGNcdWI5N2MgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YjJlNCBcdWM5YzBcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWI5YzhcdWM3NDQgXHVjODA0XHVjNWVkXHVjNWQwXHVjMTFjIFx1YzBkZFx1YzBiMFx1YjQxOFx1YjI5NCBcdWQxYjVcdWIwOThcdWJiMzRcdWI5N2MgJnF1b3Q7XHVjODAxXHViMmY5XHVkNTVjIFx1YmFhOVx1YWNmNVx1YzE4Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzJnF1b3Q7XHVhZTRjXHVjOWMwIFx1YWMxNVx1YzczY1x1Yjg1YyBcdWM2YjRcdWJjMThcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1Y2QxZCBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvdGVtcDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTc3cHg7IHdpZHRoOjI3NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjMTIwXHViZDg0XHVjNzQwIFx1YWMxNVx1Yzc0NCBcdWI3M2JcdWQ1NThcdWFjZTAsIFx1YzZkMFx1YzczY1x1Yjg1YyBcdWI0MWMgXHVjODE1XHVjODEwXHVjNzQwIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YmQ4NCBcdWM3MDRcdWM3NTggXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU3NFx1YjJmOSBcdWFkNmNcdWFjMDRcdWM3NTggXHVhYzcwXHViOWFjXHVjNzc0XHViYTcwLCBcdWM2ZDAgXHVjNTQ4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWI5YzhcdWM3NDQgXHViYzg4XHVkNjM4LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNmQwIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhZGY4IFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyBcdWI5ZTRcdWIxNDQgXHVjMGRkXHVjMGIwXHViNDE4XHViMjk0IFx1ZDFiNVx1YjA5OFx1YmIzNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHViYWE5XHVhY2Y1XHVjMThjXHViOTdjIFx1YzljMFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzcwNFx1Y2U1OCBcdWI0NTAgXHVhY2YzXHVjNzQwIDJcdWJjODhcdWFjZmMgM1x1YmM4OCBcdWI5YzhcdWM3NDRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgNFx1YmM4OCBcdWI5YzhcdWM3NDRcdWM3NTggXHVkMWI1XHViMDk4XHViYjM0XHViOTdjIDJcdWJjODggXHViOWM4XHVjNzQ0XHViODVjIFx1YmNmNFx1YjBiNFx1YjI5NCBcdWJlNDRcdWM2YTkgMSZ0aW1lczszXHVhY2ZjLCAxXHViYzg4IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWQxYjVcdWIwOThcdWJiMzRcdWI5N2MgXHVjNTkxXHVkNTZkXHVjMmI5IFx1YzY1NVx1YWQ2ZFx1YzczY1x1Yjg1YyBcdWJjZjRcdWIwYjRcdWIyOTQgXHViZTQ0XHVjNmE5IDEmdGltZXM7MVx1YjljY1x1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUml2ZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5OZWFybHkgYWxsIG9mIHRoZSBLaW5nZG9tIG9mIEJ5dGVsYW5kIGlzIGNvdmVyZWQgYnkgZm9yZXN0cyBhbmQgcml2ZXJzLiBTbWFsbCByaXZlcnMgbWVldCB0byBmb3JtIGJpZ2dlciByaXZlcnMsIHdoaWNoIGFsc28gbWVldCBhbmQsIGluIHRoZSBlbmQsIGFsbCB0aGUgcml2ZXJzIFx1ZmIwMm93IHRvZ2V0aGVyIGludG8gb25lIGJpZyByaXZlci4gVGhlIGJpZyByaXZlciBtZWV0cyB0aGUgc2VhIG5lYXIgQnl0ZXRvd24uPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBuIGx1bWJlcmphY2tzJnJzcXVvOyB2aWxsYWdlcyBpbiBCeXRlbGFuZCwgZWFjaCBwbGFjZWQgbmVhciBhIHJpdmVyLiBDdXJyZW50bHksIHRoZXJlIGlzIGEgYmlnIHNhd21pbGwgaW4gQnl0ZXRvd24gdGhhdCBwcm9jZXNzZXMgYWxsIHRyZWVzIGN1dCBpbiB0aGUgS2luZ2RvbS4gVGhlIHRyZWVzIFx1ZmIwMm9hdCBmcm9tIHRoZSB2aWxsYWdlcyBkb3duIHRoZSByaXZlcnMgdG8gdGhlIHNhd21pbGwgaW4gQnl0ZXRvd24uIFRoZSBraW5nIG9mIEJ5dGVsYW5kIGRlY2lkZWQgdG8gYnVpbGQgayBhZGRpdGlvbmFsIHNhd21pbGxzIGluIHZpbGxhZ2VzIHRvIHJlZHVjZSB0aGUgY29zdCBvZiB0cmFuc3BvcnRpbmcgdGhlIHRyZWVzIGRvd25yaXZlci4gQWZ0ZXIgYnVpbGRpbmcgdGhlIHNhd21pbGxzLCB0aGUgdHJlZXMgbmVlZCBub3QgXHVmYjAyb2F0IHRvIEJ5dGV0b3duLCBidXQgY2FuIGJlIHByb2Nlc3NlZCBpbiB0aGUgXHVmYjAxcnN0IHNhd21pbGwgdGhleSBlbmNvdW50ZXIgZG93bnJpdmVyLiBPYnZpb3VzbHksIHRoZSB0cmVlcyBjdXQgbmVhciBhIHZpbGxhZ2Ugd2l0aCBhIHNhd21pbGwgbmVlZCBub3QgYmUgdHJhbnNwb3J0ZWQgYnkgcml2ZXIuIEl0IHNob3VsZCBiZSBub3RlZCB0aGF0IHRoZSByaXZlcnMgaW4gQnl0ZWxhbmQgZG8gbm90IGZvcmsuIFRoZXJlZm9yZSwgZm9yIGVhY2ggdmlsbGFnZSwgdGhlcmUgaXMgYSB1bmlxdWUgd2F5IGRvd25yaXZlciBmcm9tIHRoZSB2aWxsYWdlIHRvIEJ5dGV0b3duLjxcL3A+XHJcblxyXG48cD5UaGUga2luZyZyc3F1bztzIGFjY291bnRhbnRzIGNhbGN1bGF0ZWQgaG93IG1hbnkgdHJlZXMgYXJlIGN1dCBieSBlYWNoIHZpbGxhZ2UgcGVyIHllYXIuIFlvdSBtdXN0IGRlY2lkZSB3aGVyZSB0byBidWlsZCB0aGUgc2F3bWlsbHMgdG8gbWluaW1pemUgdGhlIHRvdGFsIGNvc3Qgb2YgdHJhbnNwb3J0aW5nIHRoZSB0cmVlcyBwZXIgeWVhci4gUml2ZXIgdHJhbnNwb3J0YXRpb24gY29zdHMgb25lIGNlbnQgcGVyIGtpbG9tZXRyZSwgcGVyIHRyZWUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBudW1iZXIgb2YgdmlsbGFnZXMsIHRoZSBudW1iZXIgb2YgYWRkaXRpb25hbCBzYXdtaWxscyB0byBiZSBidWlsdCwgdGhlIG51bWJlciBvZiB0cmVlcyBjdXQgbmVhciBlYWNoIHZpbGxhZ2UsIGFuZCBkZXNjcmlwdGlvbnMgb2YgdGhlIHJpdmVycyw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyB0aGUgbWluaW1hbCBjb3N0IG9mIHJpdmVyIHRyYW5zcG9ydGF0aW9uIGFmdGVyIGJ1aWxkaW5nIGFkZGl0aW9uYWwgc2F3bWlsbHMsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnM6IG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHZpbGxhZ2VzIG90aGVyIHRoYW4gQnl0ZXRvd24gKDIgJmxlOyBuICZsZTsgMTAwKSwgYW5kIGsgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGFkZGl0aW9uYWwgc2F3bWlsbHMgdG8gYmUgYnVpbHQgKDEgJmxlOyBrICZsZTsgNTAgYW5kIGsgJmxlOyBuKS4gVGhlIHZpbGxhZ2VzIGFyZSBudW1iZXJlZCAxLDIsLi4uLG4sIHdoaWxlIEJ5dGV0b3duIGhhcyBudW1iZXIgMC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBMaW5lIGkrMSBjb250YWluczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT53PHN1Yj5pPFwvc3ViPiAmbWRhc2g7IHRoZSBudW1iZXIgb2YgdHJlZXMgY3V0IG5lYXIgdmlsbGFnZSBpIHBlciB5ZWFyICgwICZsZTsgdzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCksPFwvbGk+XHJcblx0PGxpPnY8c3ViPmk8XC9zdWI+ICZtZGFzaDsgdGhlIFx1ZmIwMXJzdCB2aWxsYWdlIChvciBCeXRldG93bikgZG93bnJpdmVyIGZyb20gdmlsbGFnZSBpICgwICZsZTsgdjxzdWI+aTxcL3N1Yj4gJmxlOyBuKSw8XC9saT5cclxuXHQ8bGk+ZDxzdWI+aTxcL3N1Yj4gJm1kYXNoOyB0aGUgZGlzdGFuY2UgKGluIGtpbG9tZXRyZXMpIGJ5IHJpdmVyIGZyb20gdmlsbGFnZSBpIHRvIHY8c3ViPmk8XC9zdWI+ICgxICZsZTsgZDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSB0b3RhbCBjb3N0IG9mIFx1ZmIwMm9hdGluZyBhbGwgdGhlIHRyZWVzIHRvIHRoZSBzYXdtaWxsIGluIEJ5dGV0b3duIGluIG9uZSB5ZWFyIGRvZXMgbm90IGV4Y2VlZCAyMDAwMDAwMDAwIGNlbnRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyOiB0aGUgbWluaW1hbCBjb3N0IG9mIHJpdmVyIHRyYW5zcG9ydGF0aW9uIChpbiBjZW50cykuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcml2LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1N3B4OyB3aWR0aDoyNTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgYWJvdmUgcGljdHVyZSBpbGx1c3RyYXRlcyB0aGUgZXhhbXBsZSBpbnB1dCBkYXRhLiBWaWxsYWdlIG51bWJlcnMgYXJlIGdpdmVuIGluc2lkZSBjaXJjbGVzLiBOdW1iZXJzIGJlbG93IHRoZSBjaXJjbGVzIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiB0cmVlcyBjdXQgbmVhciB2aWxsYWdlcy4gTnVtYmVycyBhYm92ZSB0aGUgYXJyb3dzIHJlcHJlc2VudCByaXZlcnMmcnNxdW87IGxlbmd0aHMuPFwvcD5cclxuXHJcbjxwPlRoZSBzYXdtaWxscyBzaG91bGQgYmUgYnVpbHQgaW4gdmlsbGFnZXMgMiBhbmQgMy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2005 6번