시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 161 27 20 19.608%

문제

요즘 고려대학교에서 가장 유행하는 게임은 "구슬을 꿰어라" 이다. 게임 이름에서 알 수 있듯이 이 게임은 구슬과 실을 이용해서 한다. 실은 총 두 가지 색상이 있고, 빨간색과 파란색이다. 구슬은 1번부터 n번가지 번호가 매겨져 있다. 게임은 구슬 1개를 가지고 시작한다. 이제 다음과 같은 과정을 통해 새로운 구슬을 실을 이용해 추가할 수 있다.

  • Append(w, v): 새로운 구슬 w를 이미 가지고 있는 구슬 v에 빨간 실을 이용해 연결한다.
  • Insert(w, u, v): 새로운 구슬 w를 이미 빨간 실로 연결된 구슬 u와 v사이에 파란 실 두 개를 이용해 연결한다. 이 때, u와 v를 연결하는 빨간 실은 제거해야 한다. 즉, 이미 존재하는 빨간 실 u - v가 새로운 파란 실 두 개 u - w, w - v로 교체된다.

모든 실은 특정 길이를 가진다. 게임이 종료되었을 때, 최종 점수는 구슬을 연결하는 파란 실 길이의 합이다.

게임이 모두 종료된 상태가 주어진다. 상태는 실이 연결하고 있는 두 구슬의 번호와 길이로 이루어져 있으며, 색상은 알 수 없다.

문제에서 주어진 연결 상태를 만드는 방법은 여러가지가 있다. 이 때, 모든 방법 중에서 가장 큰 최종 점수를 구하는 프로그램을 작성하시오.

입력

첫재 줄에 구슬의 수 n이 주어진다. (1 ≤ n ≤ 200000) 구슬은 1번부터 n번가지 번호가 매겨져 있다. 다음 n-1개 줄에는 실의 정보 ai, bi, ci가 주어진다. (1 ≤ ai < bi ≤ n, 1 ≤ ci ≤ 10000) ai와 bi는 실이 연결하는 구슬의 번호이고, ci는 길이이다.

출력

가능한 점수 중에서 가장 큰 최종 점수를 출력한다.

예제 입력 1

5
1 2 10
1 3 40
1 4 15
1 5 20

예제 출력 1

60

힌트

예제의 경우에 아래와 같이 연결하면, 60점을 얻을 수 있다. 시작은 3번 구슬로 시작한다.

  • 5와 3을 연결한다. (선의 길이는 상관없다)
  • 1을 3-5 사이에 넣는다. (길이 40, 20 선을 이용)
  • 2와 1을 길이가 10인 선을 이용해 연결한다.
  • 4와 1을 길이가 15인 선으로 연결한다.

연결은 아래와 같아지고, 이 방법보다 더 큰 점수를 얻을 수 있는 방법은 없다.

W3sicHJvYmxlbV9pZCI6IjEwMDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDZjXHVjMmFjXHVjNzc0IFx1YzExY1x1YjlkMFx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWFmZjBcdWM1YjRcdWM1N2MgXHViY2Y0XHViYzMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2OTRcdWM5OTggXHVhY2UwXHViODI0XHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3MjBcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQwICZxdW90O1x1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWFmZjBcdWM1YjRcdWI3N2MmcXVvdDsgXHVjNzc0XHViMmU0LiBcdWFjOGNcdWM3ODQgXHVjNzc0XHViOTg0XHVjNWQwXHVjMTFjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViNGVmXHVjNzc0IFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVhZDZjXHVjMmFjXHVhY2ZjIFx1YzJlNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkNTVjXHViMmU0LiBcdWMyZTRcdWM3NDAgXHVjZDFkIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHViZTY4XHVhYzA0XHVjMGM5XHVhY2ZjIFx1ZDMwY1x1Yjc4MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHVhZDZjXHVjMmFjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWMwMFx1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQwIFx1YWQ2Y1x1YzJhYyAxXHVhYzFjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjMGM4XHViODVjXHVjNmI0IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWMyZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Y2Q5NFx1YWMwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkFwcGVuZCh3LCB2KTogXHVjMGM4XHViODVjXHVjNmI0IFx1YWQ2Y1x1YzJhYyB3XHViOTdjIFx1Yzc3NFx1YmJmOCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhYyB2XHVjNWQwIFx1YmU2OFx1YWMwNCBcdWMyZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+SW5zZXJ0KHcsIHUsIHYpOiBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZDZjXHVjMmFjIHdcdWI5N2MgXHVjNzc0XHViYmY4IFx1YmU2OFx1YWMwNCBcdWMyZTRcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQ2Y1x1YzJhYyB1XHVjNjQwIHZcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkMzBjXHViNzgwIFx1YzJlNCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIHVcdWM2NDAgdlx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViZTY4XHVhYzA0IFx1YzJlNFx1Yzc0MCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1Yzc3NFx1YmJmOCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViZTY4XHVhYzA0IFx1YzJlNCB1IC0gdlx1YWMwMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVkMzBjXHViNzgwIFx1YzJlNCBcdWI0NTAgXHVhYzFjIHUgLSB3LCB3IC0gdlx1Yjg1YyBcdWFkNTBcdWNjYjRcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzJlNFx1Yzc0MCBcdWQyYjlcdWM4MTUgXHVhZTM4XHVjNzc0XHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQxOFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1Yzg4NSBcdWM4MTBcdWMyMThcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWI3ODAgXHVjMmU0IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjODg1XHViOGNjXHViNDFjIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWMyZTRcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWFlMzhcdWM3NzRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMGM5XHVjMGMxXHVjNzQwIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzVmMFx1YWNiMCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViYzI5XHViYzk1IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1Y2Q1Y1x1Yzg4NSBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDIwMDAwMCkmbmJzcDtcdWFkNmNcdWMyYWNcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBuXHViYzg4XHVhYzAwXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgbi0xXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZTRcdWM3NTggXHVjODE1XHViY2Y0IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiwgYzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsdDsgYjxzdWI+aTxcL3N1Yj4gJmxlOyBuLCAxICZsZTsgYzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCkgYTxzdWI+aTxcL3N1Yj5cdWM2NDAgYjxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVjMmU0XHVjNzc0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBjPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YzgxMFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWNkNWNcdWM4ODUgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YmE3NCwgNjBcdWM4MTBcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzJkY1x1Yzc5MVx1Yzc0MCAzXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+NVx1YzY0MCAzXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gKFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0KTxcL2xpPlxyXG5cdDxsaT4xXHVjNzQ0IDMtNSBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiAoXHVhZTM4XHVjNzc0IDQwLCAyMCBcdWMxMjBcdWM3NDQgXHVjNzc0XHVjNmE5KTxcL2xpPlxyXG5cdDxsaT4yXHVjNjQwIDFcdWM3NDQgXHVhZTM4XHVjNzc0XHVhYzAwIDEwXHVjNzc4IFx1YzEyMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT40XHVjNjQwIDFcdWM3NDQgXHVhZTM4XHVjNzc0XHVhYzAwIDE1XHVjNzc4IFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNWYwXHVhY2IwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM1NDRcdWM5YzBcdWFjZTAsIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWJjZjRcdWIyZTQgXHViMzU0IFx1ZDA3MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iZWFkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyN3B4OyB3aWR0aDoyNDBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwNjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCZWFkcyBhbmQgd2lyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcG9wdWxhciBjaGlsZCBnYW1lIGF0IHRoZSB0aW1lIG9mIExlb25hcmRvIHdhcyBjYWxsZWQgQmVhZHMtYW5kLXdpcmVzLiBOb3Qgc3VycHJpc2luZ2x5LCBpdCB3YXMgcGxheWVkIHdpdGggYmVhZHMgYW5kIHdpcmVzLiBUaGUgd2lyZXMgYXJlIHJlZCBvciBibHVlLiBUaGUgYmVhZHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGUgZ2FtZSBzdGFydHMgd2l0aCBhIHNpbmdsZSBiZWFkLiBGcm9tIHRoaXMgbW9tZW50IG9uLCBuZXcgYmVhZHMgY2FuIGJlIGFkZGVkIHVzaW5nIHdpcmVzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QXBwZW5kKHcsIHYpOiBhIG5ldyBiZWFkIHcgaXMgYXR0YWNoZWQgdG8gYW4gZXhpc3RpbmcgYmVhZCB2IHRocm91Z2ggYSBwaWVjZSBvZiByZWQgd2lyZS48XC9saT5cclxuXHQ8bGk+SW5zZXJ0KHcsIHUsIHYpOiBhIG5ldyBiZWFkIHcgaXMgaW5zZXJ0ZWQgYnkgc3Vic3RpdHV0aW5nIGFuIGFscmVhZHkgZXhpc3RpbmcgcmVkIHdpcmUgY29ubmVjdGluZyBleGlzdGluZyBiZWFkcyB1IGFuZCB2LCB3aXRoIHR3byBuZXcgYmx1ZSB3aXJlcyBieSBwdXR0aW5nIHcgYmV0d2VlbiB1IGFuZCB2OyBpbiBvdGhlciB3b3JkcywgdGhlIGV4aXN0aW5nIHJlZCB3aXJlIHUgJm1pbnVzOyB2IGlzIHJlcGxhY2VkIGJ5IHR3byBuZXcgYmx1ZSB3aXJlcyB1ICZtaW51czsgdyBhbmQgdyAmbWludXM7IHYuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RXZlcnkgcGllY2Ugb2Ygd2lyZSAoYm90aCBibHVlIG9yIHJlZCkgaGFzIGEgY2VydGFpbiBsZW5ndGguIEF0IHRoZSBlbmQgb2YgdGhlIGdhbWUsIHdoYXQgY291bnRzIGlzIHRoZSBzdW0gb2YgbGVuZ3RocyBvZiBibHVlIHdpcmVzIG9ubHkgKHRoZSBsZW5ndGggb2YgcmVkIHdpcmVzIGRvZXNuJnJzcXVvO3QgY291bnQpOiB0aGlzIGlzIGNhbGxlZCB0aGUgZmluYWwgc2NvcmUuIFlvdSBhcmUgZ2l2ZW4gdGhlIGZpbmFsIGNvbmZpZ3VyYXRpb24gcmVhY2hlZCBieSBhIGJlYWRzLWFuZC13aXJlIGdhbWUsIHNwZWNpZnlpbmcgaG93IGJlYWRzIGFyZSBjb25uZWN0ZWQgdG8gb25lIGFub3RoZXIgYW5kIHByb3ZpZGluZyBhbHNvIHRoZSBsZW5ndGggb2YgZWFjaCBwaWVjZSBvZiB3aXJlLCBidXQgb21pdHRpbmcgdGhlIGNvbG9yIG9mIHRoZSB3aXJlcy48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG1heGltYWwgcG9zc2libGUgZmluYWwgc2NvcmUgZm9yIHRoYXQgY29uZmlndXJhdGlvbi4gTW9yZSBwcmVjaXNlbHksIGFtb25nIGFsbCB0aGUgZmVhc2libGUgYmVhZHMtYW5kLXdpcmUgZ2FtZXMgdGhhdCBlbmQgd2l0aCB0aGF0IGNvbmZpZ3VyYXRpb24sIHlvdSBoYXZlIHRvIGZpbmQgb25lIHRoYXQgaGFzIHRoZSBtYXhpbXVtIGZpbmFsIHNjb3JlIChzdW0gb2YgYmx1ZSB3aXJlIGxlbmd0aCkgYW5kIHlvdSBoYXZlIHRvIG91dHB1dCB0aGF0IHZhbHVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyBwb3NpdGl2ZSBpbnRlZ2VyIG4gJm1kYXNoOyBudW1iZXIgb2YgYmVhZHMsIHdoaWNoIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gTmV4dCBuICZtaW51czsgMSBsaW5lcyBjb250YWlucyAzIG51bWJlcnMgZWFjaDogYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmx0OyBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4pIGFuZCAxICZsZTsgYzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCAmbWRhc2g7IHR3byBiZWFkcyBjb25uZWN0ZWQgYnkgYSBwaWVjZSBvZiB3aXJlLCBhbmQgdGhlIGxlbmd0aCBvZiB0aGF0IHBpZWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciAmbmRhc2g7IHRoZSBtYXhpbXVtIGZpbmFsIHNjb3JlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgdGhlIGZpcnN0IHNhbXBsZSB0ZXN0Y2FzZSwgdGhlIGZpbmFsIHNjb3JlIG9mIDYwIGNhbiBiZSBvYnRhaW5lZCBhcyBmb2xsb3dzOiBzdGFydCB3aXRoIHRoZSBzaW5nbGUgYmVhZCAzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmFwcGVuZCA1IHRvIDMgKHdpdGggYSB3aXJlIG9mIGFyYml0cmFyeSBsZW5ndGgpLjxcL2xpPlxyXG5cdDxsaT5pbnNlcnQgMSBvbiB0aGUgd2lyZSAzICZtaW51czsgNSAodXNpbmcgd2lyZXMgb2YgbGVuZ3RoIDQwIGFuZCAyMCkuPFwvbGk+XHJcblx0PGxpPmFwcGVuZCAyIHRvIDEgd2l0aCBhIHdpcmUgb2YgbGVuZ3RoIDEwLjxcL2xpPlxyXG5cdDxsaT5hcHBlbmQgNCB0byAxIHdpdGggYSB3aXJlIG9mIGxlbmd0aCAxNS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgY29uZmlndXJhdGlvbiBvYnRhaW5lZCB0aGlzIHdheSBpcyBzaG93biBpbiB0aGUgZmlyc3QgZmlndXJlLiBJdCBpcyBwb3NzaWJsZSB0byBzZWUgdGhhdCB0aGVyZSBpcyBubyB3YXkgdG8gb2J0YWluIHRoZSBzYW1lIGNvbmZpZ3VyYXRpb24gKGFwYXJ0IGZvciB0aGUgY29sb3JzKSB3aXRoIGEgbGFyZ2VyIGZpbmFsIHNjb3JlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JlYWQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IHdpZHRoOjI0MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2014 3번