시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 163 28 21 20.000%

문제

요즘 고려대학교에서 가장 유행하는 게임은 "구슬을 꿰어라" 이다. 게임 이름에서 알 수 있듯이 이 게임은 구슬과 실을 이용해서 한다. 실은 총 두 가지 색상이 있고, 빨간색과 파란색이다. 구슬은 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+SW5zZXJ0KHcsIHUsIHYpOiBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZDZjXHVjMmFjIHdcdWI5N2MgXHVjNzc0XHViYmY4IFx1YmU2OFx1YWMwNCBcdWMyZTRcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQ2Y1x1YzJhYyB1XHVjNjQwIHZcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkMzBjXHViNzgwIFx1YzJlNCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgdVx1YzY0MCB2XHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJlNjhcdWFjMDQgXHVjMmU0XHVjNzQwIFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjNzc0XHViYmY4IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWJlNjhcdWFjMDQgXHVjMmU0IHUgLSB2XHVhYzAwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQzMGNcdWI3ODAgXHVjMmU0IFx1YjQ1MCBcdWFjMWMgdSAtIHcsIHcgLSB2XHViODVjIFx1YWQ1MFx1Y2NiNFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjMmU0XHVjNzQwIFx1ZDJiOVx1YzgxNSBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjODg1XHViOGNjXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHVjODg1IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDMwY1x1Yjc4MCBcdWMyZTQgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM4ODVcdWI4Y2NcdWI0MWMgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGMxXHVkMGRjXHViMjk0IFx1YzJlNFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjQ1MCBcdWFkNmNcdWMyYWNcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YWUzOFx1Yzc3NFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNWYwXHVhY2IwIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTUgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjZDVjXHVjODg1IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMjAwMDAwKSZuYnNwO1x1YWQ2Y1x1YzJhY1x1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFjMDBcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzJlNFx1Yzc1OCBcdWM4MTVcdWJjZjQgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+LCBjPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmx0OyBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4sIDEgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwKSBhPHN1Yj5pPFwvc3ViPlx1YzY0MCBiPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWMyZTRcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIGM8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVjODEwXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1Y2Q1Y1x1Yzg4NSBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTc0LCA2MFx1YzgxMFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMmRjXHVjNzkxXHVjNzQwIDNcdWJjODggXHVhZDZjXHVjMmFjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT41XHVjNjQwIDNcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiAoXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQpPFwvbGk+XHJcblx0PGxpPjFcdWM3NDQgMy01IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuIChcdWFlMzhcdWM3NzQgNDAsIDIwIFx1YzEyMFx1Yzc0NCBcdWM3NzRcdWM2YTkpPFwvbGk+XHJcblx0PGxpPjJcdWM2NDAgMVx1Yzc0NCBcdWFlMzhcdWM3NzRcdWFjMDAgMTBcdWM3NzggXHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjRcdWM2NDAgMVx1Yzc0NCBcdWFlMzhcdWM3NzRcdWFjMDAgMTVcdWM3NzggXHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1ZjBcdWFjYjBcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YzU0NFx1YzljMFx1YWNlMCwgXHVjNzc0IFx1YmMyOVx1YmM5NVx1YmNmNFx1YjJlNCBcdWIzNTQgXHVkMDcwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JlYWQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IHdpZHRoOjI0MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDA2OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlYWRzIGFuZCB3aXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBwb3B1bGFyIGNoaWxkIGdhbWUgYXQgdGhlIHRpbWUgb2YgTGVvbmFyZG8gd2FzIGNhbGxlZCBCZWFkcy1hbmQtd2lyZXMuIE5vdCBzdXJwcmlzaW5nbHksIGl0IHdhcyBwbGF5ZWQgd2l0aCBiZWFkcyBhbmQgd2lyZXMuIFRoZSB3aXJlcyBhcmUgcmVkIG9yIGJsdWUuIFRoZSBiZWFkcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFRoZSBnYW1lIHN0YXJ0cyB3aXRoIGEgc2luZ2xlIGJlYWQuIEZyb20gdGhpcyBtb21lbnQgb24sIG5ldyBiZWFkcyBjYW4gYmUgYWRkZWQgdXNpbmcgd2lyZXMgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BcHBlbmQodywgdik6IGEgbmV3IGJlYWQgdyBpcyBhdHRhY2hlZCB0byBhbiBleGlzdGluZyBiZWFkIHYgdGhyb3VnaCBhIHBpZWNlIG9mIHJlZCB3aXJlLjxcL2xpPlxyXG5cdDxsaT5JbnNlcnQodywgdSwgdik6IGEgbmV3IGJlYWQgdyBpcyBpbnNlcnRlZCBieSBzdWJzdGl0dXRpbmcgYW4gYWxyZWFkeSBleGlzdGluZyByZWQgd2lyZSBjb25uZWN0aW5nIGV4aXN0aW5nIGJlYWRzIHUgYW5kIHYsIHdpdGggdHdvIG5ldyBibHVlIHdpcmVzIGJ5IHB1dHRpbmcgdyBiZXR3ZWVuIHUgYW5kIHY7IGluIG90aGVyIHdvcmRzLCB0aGUgZXhpc3RpbmcgcmVkIHdpcmUgdSAmbWludXM7IHYgaXMgcmVwbGFjZWQgYnkgdHdvIG5ldyBibHVlIHdpcmVzIHUgJm1pbnVzOyB3IGFuZCB3ICZtaW51czsgdi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5FdmVyeSBwaWVjZSBvZiB3aXJlIChib3RoIGJsdWUgb3IgcmVkKSBoYXMgYSBjZXJ0YWluIGxlbmd0aC4gQXQgdGhlIGVuZCBvZiB0aGUgZ2FtZSwgd2hhdCBjb3VudHMgaXMgdGhlIHN1bSBvZiBsZW5ndGhzIG9mIGJsdWUgd2lyZXMgb25seSAodGhlIGxlbmd0aCBvZiByZWQgd2lyZXMgZG9lc24mcnNxdW87dCBjb3VudCk6IHRoaXMgaXMgY2FsbGVkIHRoZSBmaW5hbCBzY29yZS4gWW91IGFyZSBnaXZlbiB0aGUgZmluYWwgY29uZmlndXJhdGlvbiByZWFjaGVkIGJ5IGEgYmVhZHMtYW5kLXdpcmUgZ2FtZSwgc3BlY2lmeWluZyBob3cgYmVhZHMgYXJlIGNvbm5lY3RlZCB0byBvbmUgYW5vdGhlciBhbmQgcHJvdmlkaW5nIGFsc28gdGhlIGxlbmd0aCBvZiBlYWNoIHBpZWNlIG9mIHdpcmUsIGJ1dCBvbWl0dGluZyB0aGUgY29sb3Igb2YgdGhlIHdpcmVzLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbWF4aW1hbCBwb3NzaWJsZSBmaW5hbCBzY29yZSBmb3IgdGhhdCBjb25maWd1cmF0aW9uLiBNb3JlIHByZWNpc2VseSwgYW1vbmcgYWxsIHRoZSBmZWFzaWJsZSBiZWFkcy1hbmQtd2lyZSBnYW1lcyB0aGF0IGVuZCB3aXRoIHRoYXQgY29uZmlndXJhdGlvbiwgeW91IGhhdmUgdG8gZmluZCBvbmUgdGhhdCBoYXMgdGhlIG1heGltdW0gZmluYWwgc2NvcmUgKHN1bSBvZiBibHVlIHdpcmUgbGVuZ3RoKSBhbmQgeW91IGhhdmUgdG8gb3V0cHV0IHRoYXQgdmFsdWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGNvbnRhaW5zIHBvc2l0aXZlIGludGVnZXIgbiAmbWRhc2g7IG51bWJlciBvZiBiZWFkcywgd2hpY2ggYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBOZXh0IG4gJm1pbnVzOyAxIGxpbmVzIGNvbnRhaW5zIDMgbnVtYmVycyBlYWNoOiBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbHQ7IGI8c3ViPmk8XC9zdWI+ICZsZTsgbikgYW5kIDEgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwICZtZGFzaDsgdHdvIGJlYWRzIGNvbm5lY3RlZCBieSBhIHBpZWNlIG9mIHdpcmUsIGFuZCB0aGUgbGVuZ3RoIG9mIHRoYXQgcGllY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyICZuZGFzaDsgdGhlIG1heGltdW0gZmluYWwgc2NvcmUuPFwvcD5cclxuIiwiaGludCI6IjxwPkZvciB0aGUgZmlyc3Qgc2FtcGxlIHRlc3RjYXNlLCB0aGUgZmluYWwgc2NvcmUgb2YgNjAgY2FuIGJlIG9idGFpbmVkIGFzIGZvbGxvd3M6IHN0YXJ0IHdpdGggdGhlIHNpbmdsZSBiZWFkIDMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+YXBwZW5kIDUgdG8gMyAod2l0aCBhIHdpcmUgb2YgYXJiaXRyYXJ5IGxlbmd0aCkuPFwvbGk+XHJcblx0PGxpPmluc2VydCAxIG9uIHRoZSB3aXJlIDMgJm1pbnVzOyA1ICh1c2luZyB3aXJlcyBvZiBsZW5ndGggNDAgYW5kIDIwKS48XC9saT5cclxuXHQ8bGk+YXBwZW5kIDIgdG8gMSB3aXRoIGEgd2lyZSBvZiBsZW5ndGggMTAuPFwvbGk+XHJcblx0PGxpPmFwcGVuZCA0IHRvIDEgd2l0aCBhIHdpcmUgb2YgbGVuZ3RoIDE1LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBjb25maWd1cmF0aW9uIG9idGFpbmVkIHRoaXMgd2F5IGlzIHNob3duIGluIHRoZSBmaXJzdCBmaWd1cmUuIEl0IGlzIHBvc3NpYmxlIHRvIHNlZSB0aGF0IHRoZXJlIGlzIG5vIHdheSB0byBvYnRhaW4gdGhlIHNhbWUgY29uZmlndXJhdGlvbiAoYXBhcnQgZm9yIHRoZSBjb2xvcnMpIHdpdGggYSBsYXJnZXIgZmluYWwgc2NvcmUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmVhZC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjdweDsgd2lkdGg6MjQwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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