시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 164 69 60 46.154%

문제

20XX년에 IOI나라에서 열리는 올림픽 준비의 일환으로 IOI나라에 있는 JOI공원을 정비하기로 했다. JOI공원에는 N개의 광장이 있고, 1부터 N까지 번호가 붙어 있다. 또, 공원에는 광장을 연결하는 M개의 도로가 있고, 1부터 M까지 번호가 붙어있다. 도로 i (1 ≦ i ≦ M)는 광장 Ai와 광장 Bi를 쌍방향으로 연결하며 그 길이는 Di이다. 어떤 광장에서도 한 개 이상의 도로를 통해서 다른 광장으로 가는 것이 가능하다.

정비계획은 다음과 같다. 지하도 설치에 관한 변수 C가 주어진다. 먼저, 0 이상의 정수 X를 고르고 광장 1로부터 거리가 X이하인 광장(광장 1을 포함해서) 모두를 지하도로 연결한다. 단, 광장 i와 광장 j의 거리는 광장 i로부터 광장 j까지 가는 데 걸리는 도로의 길이의 최소로 정의한다. 지하도를 설치하는 데에 드는 전체 비용은 C × X이다.

다음으로, 지하도로 연결된 광장들을 잇는 도로를 전부 철거한다. 도로를 철거하는 데에 비용은 들지 않는다.

마지막으로, 철거되지 않고 남은 도로를 전부 보수한다. 길이 d의 도로를 보수하는데에 드는 비용은 d이다.

정비계획을 실시하기 전, JOI공원에 지하도는 없다. JOI공원에 있는 광장의 정보와 지하도 설치 비용이 주어질 때, JOI공원을 정비하는 데에 드는 비용의 최솟값을 구하는 프로그램을 작성하여라.

입력

표준입력으로 다음의 정보가 주어진다.

  • 첫 번째 줄에는 정수 N,M,C가 공백을 두고 주어진다. 이것은 광장이 N개, 도로가 M개 있고, 지하도 설치에 관한 변수가 C라는 것을 의미한다.
  • 다음 M개 행에서는 정수 Ai,Bi,Di (1 ≦ i ≦ M) 가 공백을 두고 한 줄씩 주어진다. 이것은 도로 i가 광장 Ai와 Bi를 잇고, 그 길이가 Di라는 것을 의미한다.
모든 입력 데이터는 아래의 조건을 만족한다.
  • 2 ≦ N ≦ 100 000.
  • 1 ≦ M ≦ 200 000.
  • 1 ≦ C ≦ 100 000.
  • 1 ≦ Ai ≦ N (1 ≦ i ≦ M).
  • 1 ≦ Bi ≦ N (1 ≦ i ≦ M).
  • Ai ≠ Bi (1 ≦ i ≦ M).
  • (Ai, Bi) ≠ (Aj, Bj) 및 (Ai, Bi) ≠ (Bj, Aj) (1 ≦ i < j ≦ M).
  • 1 ≦ Di ≦ 100 000 (1 ≦ i ≦ M).
  • 주어지는 입력 데이터에 대해서는 어떤 광장에서도 한 개 이상의 도로를 통해서 다른 광장으로 갈 수 있는 것이 보증된다.

출력

JOI공원 정비에 드는 비용의 최솟값을 1줄로 출력한다.

예제 입력 1

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

예제 출력 1

14

예제 입력 2

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

예제 출력 2

15

예제 입력 3

6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5

예제 출력 3

10

힌트

이 입력예제에서는 X = 3으로 하여 광장 1로부터 거리가 3이하가 되는 광장(광장 1, 광장 2, 광장 3)을 전부 지하도로 이었을 경우, 정비하는 데에 드는 비용의 합은 (2 × 3) + (3 + 5) = 14이다. 이것이 최솟값이다.

W3sicHJvYmxlbV9pZCI6IjEwNzE1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSk9JIFx1YWNmNVx1YzZkMCIsImRlc2NyaXB0aW9uIjoiPHA+MjBYWFx1YjE0NFx1YzVkMCBJT0lcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWMgXHVjNWY0XHViOWFjXHViMjk0IFx1YzYyY1x1YjliY1x1ZDUzZCBcdWM5MDBcdWJlNDRcdWM3NTggXHVjNzdjXHVkNjU4XHVjNzNjXHViODVjIElPSVx1YjA5OFx1Yjc3Y1x1YzVkMCBcdWM3ODhcdWIyOTQgSk9JXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzgxNVx1YmU0NFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIEpPSVx1YWNmNVx1YzZkMFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YWQxMVx1YzdhNVx1Yzc3NCBcdWM3ODhcdWFjZTAsIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjZjVcdWM2ZDBcdWM1ZDBcdWIyOTQgXHVhZDExXHVjN2E1XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIDFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMmU0LiBcdWIzYzRcdWI4NWMgaSAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWIyOTQgXHVhZDExXHVjN2E1IEFpXHVjNjQwIFx1YWQxMVx1YzdhNSBCaVx1Yjk3YyBcdWMzMGRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwIFx1YWRmOCBcdWFlMzhcdWM3NzRcdWIyOTQgRGlcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWFkMTFcdWM3YTVcdWM1ZDBcdWMxMWNcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWIyZTRcdWI5NzggXHVhZDExXHVjN2E1XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWJlNDRcdWFjYzRcdWQ2OGRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjOWMwXHVkNTU4XHViM2M0IFx1YzEyNFx1Y2U1OFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViY2MwXHVjMjE4IENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhM2NcdWM4MDAsIDAgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxNVx1YzIxOCBYXHViOTdjIFx1YWNlMFx1Yjk3NFx1YWNlMCBcdWFkMTFcdWM3YTUgMVx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFjNzBcdWI5YWNcdWFjMDAgWFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWFkMTFcdWM3YTUoXHVhZDExXHVjN2E1IDFcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjKSBcdWJhYThcdWI0NTBcdWI5N2MgXHVjOWMwXHVkNTU4XHViM2M0XHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWFkMTFcdWM3YTUgaVx1YzY0MCBcdWFkMTFcdWM3YTUgalx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVhZDExXHVjN2E1IGlcdWI4NWNcdWJkODBcdWQxMzAgXHVhZDExXHVjN2E1IGpcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWM5YzBcdWQ1NThcdWIzYzRcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTU4XHViMjk0IFx1YjM3MFx1YzVkMCBcdWI0ZGNcdWIyOTQgXHVjODA0XHVjY2I0IFx1YmU0NFx1YzZhOVx1Yzc0MCBDICZ0aW1lczsgWFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNzNjXHViODVjLCBcdWM5YzBcdWQ1NThcdWIzYzRcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQxMVx1YzdhNVx1YjRlNFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1YzgwNFx1YmQ4MCBcdWNjYTBcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWNjYTBcdWFjNzBcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwIFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFx1Y2NhMFx1YWM3MFx1YjQxOFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMGE4XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM4MDRcdWJkODAgXHViY2Y0XHVjMjE4XHVkNTVjXHViMmU0LiBcdWFlMzhcdWM3NzQgZFx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViY2Y0XHVjMjE4XHVkNTU4XHViMjk0XHViMzcwXHVjNWQwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViZTQ0XHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzJlNFx1YzJkY1x1ZDU1OFx1YWUzMCBcdWM4MDQsIEpPSVx1YWNmNVx1YzZkMFx1YzVkMCBcdWM5YzBcdWQ1NThcdWIzYzRcdWIyOTQgXHVjNWM2XHViMmU0LiBKT0lcdWFjZjVcdWM2ZDBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQxMVx1YzdhNVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVjOWMwXHVkNTU4XHViM2M0IFx1YzEyNFx1Y2U1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgSk9JXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzgxNVx1YmU0NFx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViMmU0XHVjNzRjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IE4sTSxDXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NDAgXHVhZDExXHVjN2E1XHVjNzc0IE5cdWFjMWMsIFx1YjNjNFx1Yjg1Y1x1YWMwMCBNXHVhYzFjIFx1Yzc4OFx1YWNlMCwgXHVjOWMwXHVkNTU4XHViM2M0IFx1YzEyNFx1Y2U1OFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViY2MwXHVjMjE4XHVhYzAwIENcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVkNTg5XHVjNWQwXHVjMTFjXHViMjk0IFx1YzgxNVx1YzIxOCBBaSxCaSxEaSAoMSBcdTIyNjYgaSBcdTIyNjYgTSkgXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVkNTVjIFx1YzkwNFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWIzYzRcdWI4NWMgaVx1YWMwMCBcdWFkMTFcdWM3YTUgQWlcdWM2NDAgQmlcdWI5N2MgXHVjNzg3XHVhY2UwLCBcdWFkZjggXHVhZTM4XHVjNzc0XHVhYzAwIERpXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPGRpdj5cdWJhYThcdWI0ZTAgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWM1NDRcdWI3OThcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9kaXY+XHJcblxyXG48dWw+XHJcblx0PGxpPjIgXHUyMjY2IE4gXHUyMjY2IDEwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgTSBcdTIyNjYgMjAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBDIFx1MjI2NiAxMDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IEFpIFx1MjI2NiBOICgxIFx1MjI2NiBpIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBCaSBcdTIyNjYgTiAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+QWkgJm5lOyBCaSAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+KEFpLCBCaSkgJm5lOyAoQWosIEJqKSBcdWJjMGYgKEFpLCBCaSkgJm5lOyAoQmosIEFqKSAoMSBcdTIyNjYgaSAmbHQ7IGogXHUyMjY2IE0pXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IERpIFx1MjI2NiAxMDAgMDAwICgxIFx1MjI2NiBpIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YWQxMVx1YzdhNVx1YzVkMFx1YzExY1x1YjNjNCBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWFkMTFcdWM3YTVcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmNmNFx1Yzk5ZFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkpPSVx1YWNmNVx1YzZkMCBcdWM4MTVcdWJlNDRcdWM1ZDAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgMVx1YzkwNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgWCA9IDNcdWM3M2NcdWI4NWMgXHVkNTU4XHVjNWVjIFx1YWQxMVx1YzdhNSAxXHViODVjXHViZDgwXHVkMTMwIFx1YWM3MFx1YjlhY1x1YWMwMCAzXHVjNzc0XHVkNTU4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFkMTFcdWM3YTUoXHVhZDExXHVjN2E1IDEsIFx1YWQxMVx1YzdhNSAyLCBcdWFkMTFcdWM3YTUgMylcdWM3NDQgXHVjODA0XHViZDgwIFx1YzljMFx1ZDU1OFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM1YzhcdWM3NDQgXHVhY2JkXHVjNmIwLCBcdWM4MTVcdWJlNDRcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzQwICgyICZ0aW1lczsgMykgKyAoMyArIDUpID0gMTRcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDcxNSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IkpPSSBcdTUxNmNcdTU3MTIiLCJkZXNjcmlwdGlvbiI6IjxwPjIwWFggXHU1ZTc0XHUzMDZiIElPSSBcdTU2ZmRcdTMwNjdcdTg4NGNcdTMwOGZcdTMwOGNcdTMwOGJcdTMwYWFcdTMwZWFcdTMwZjNcdTMwZDRcdTMwYzNcdTMwYWZcdTMwNmJcdTUwOTlcdTMwNDhcdWZmMGNJT0kgXHU1NmZkXHUzMDZiXHUzMDQyXHUzMDhiIEpPSSBcdTUxNmNcdTU3MTJcdTMwOTJcdTY1NzRcdTUwOTlcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNmFcdTMwNjNcdTMwNWZcdWZmMGVKT0lcdTUxNmNcdTU3MTJcdTMwNmJcdTMwNmYgTiBcdTUwMGJcdTMwNmVcdTVlODNcdTU4MzRcdTMwNGNcdTMwNDJcdTMwOGFcdWZmMGNcdTVlODNcdTU4MzRcdTMwNmJcdTMwNmYgMSBcdTMwNGJcdTMwODkgTiBcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTMwNjRcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTVlODNcdTU4MzRcdTMwOTJcdTdlNGJcdTMwNTAgTSBcdTY3MmNcdTMwNmVcdTkwNTNcdTMwNGNcdTMwNDJcdTMwOGFcdWZmMGNcdTkwNTNcdTMwNmJcdTMwNmYgMSBcdTMwNGJcdTMwODkgTSBcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTMwNjRcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTkwNTMgaSAoMSBcdTIyNjYgaSBcdTIyNjYgTSkgXHUzMDZmXHU1ZTgzXHU1ODM0IEFpIFx1MzA2OFx1NWU4M1x1NTgzNCBCaSBcdTMwOTJcdTUzY2NcdTY1YjlcdTU0MTFcdTMwNmJcdTdlNGJcdTMwNDRcdTMwNjdcdTMwNGFcdTMwOGFcdWZmMGNcdTk1NzdcdTMwNTVcdTMwNmYgRGkgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHUzMDY5XHUzMDZlXHU1ZTgzXHU1ODM0XHUzMDRiXHUzMDg5XHUzMDY5XHUzMDZlXHU1ZTgzXHU1ODM0XHUzMDc4XHUzMDgyXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU5MDUzXHUzMDkyXHU4ZmJmXHUzMDYzXHUzMDY2XHU4ODRjXHUzMDRmXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NjU3NFx1NTA5OVx1OGEwOFx1NzUzYlx1MzA2N1x1MzA2Zlx1ZmYwY1x1MzA3ZVx1MzA1YVx1ZmYwYzAgXHU0ZWU1XHU0ZTBhXHUzMDZlXHU2NTc0XHU2NTcwIFggXHUzMDkyXHU5MDc4XHUzMDczXHVmZjBjXHU1ZTgzXHU1ODM0IDEgXHUzMDRiXHUzMDg5XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDRjIFggXHU0ZWU1XHU0ZTBiXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDg4XHUzMDQ2XHUzMDZhXHU1ZTgzXHU1ODM0IChcdTVlODNcdTU4MzQgMSBcdTMwOTJcdTU0MmJcdTMwODApIFx1MzA2OVx1MzA0Nlx1MzA1N1x1MzA5Mlx1MzA1OVx1MzA3OVx1MzA2Nlx1NzZmOFx1NGU5Mlx1MzA2Ylx1NTczMFx1NGUwYlx1OTA1M1x1MzA2N1x1N2Q1MFx1MzA3Nlx1ZmYwZVx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwY1x1NWU4M1x1NTgzNCBpIFx1MzA2OFx1NWU4M1x1NTgzNCBqIFx1MzA2ZVx1OGRkZFx1OTZlMlx1MzA2OFx1MzA2Zlx1ZmYwY1x1NWU4M1x1NTgzNCBpIFx1MzA0Ylx1MzA4OVx1NWU4M1x1NTgzNCBqIFx1MzA2Ylx1ODg0Y1x1MzA0Zlx1MzA2OFx1MzA0ZFx1MzA2Ylx1OTAxYVx1MzA4Ylx1OTA1M1x1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZVx1NTQ4Y1x1MzA2ZVx1NjcwMFx1NWMwZlx1NTAyNFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1NjU3NFx1NTA5OVx1OGEwOFx1NzUzYlx1MzA2N1x1MzA2Zlx1NTczMFx1NGUwYlx1OTA1M1x1MzA2ZVx1NjU3NFx1NTA5OVx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2Ylx1OTVhMlx1MzA1OVx1MzA4Ylx1NjU3NFx1NjU3MCBDIFx1MzA0Y1x1NWI5YVx1MzA3ZVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NTczMFx1NGUwYlx1OTA1M1x1MzA2ZVx1NjU3NFx1NTA5OVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2ZiBDICZ0aW1lczsgWCBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU2YjIxXHUzMDZiXHVmZjBjXHU1NzMwXHU0ZTBiXHU5MDUzXHUzMDY3XHU3ZDUwXHUzMDcwXHUzMDhjXHUzMDVmXHU1ZTgzXHU1ODM0XHUzMDY5XHUzMDQ2XHUzMDU3XHUzMDkyXHU3ZDUwXHUzMDc2XHU5MDUzXHUzMDkyXHUzMDU5XHUzMDc5XHUzMDY2XHU2NGE0XHU1M2JiXHUzMDU5XHUzMDhiXHVmZjBlXHU5MDUzXHUzMDZlXHU2NGE0XHU1M2JiXHUzMDZiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZmXHUzMDRiXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NjcwMFx1NWY4Y1x1MzA2Ylx1ZmYwY1x1NjRhNFx1NTNiYlx1MzA1NVx1MzA4Y1x1MzA1YVx1MzA2Ylx1NmI4Ylx1MzA2M1x1MzA1Zlx1OTA1M1x1MzA5Mlx1MzA1OVx1MzA3OVx1MzA2Nlx1ODhkY1x1NGZlZVx1MzA1OVx1MzA4Ylx1ZmYwZVx1OTU3N1x1MzA1NSBkIFx1MzA2ZVx1OTA1M1x1MzA5Mlx1ODhkY1x1NGZlZVx1MzA1OVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2ZiBkIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTY1NzRcdTUwOTlcdThhMDhcdTc1M2JcdTViOWZcdTY1YmRcdTUyNGRcdTMwNmUgSk9JIFx1NTE2Y1x1NTcxMlx1MzA2Ylx1MzA2Zlx1NTczMFx1NGUwYlx1OTA1M1x1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZUpPSSBcdTUxNmNcdTU3MTJcdTMwNmVcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTZjNDJcdTMwODFcdTMwODhcdWZmMGU8XC9wPlxyXG5cclxuPHA+Sk9JIFx1NTE2Y1x1NTcxMlx1MzA2ZVx1NWU4M1x1NTgzNFx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA2OFx1ZmYwY1x1NTczMFx1NGUwYlx1OTA1M1x1MzA2ZVx1NjU3NFx1NTA5OVx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2Ylx1OTVhMlx1MzA1OVx1MzA4Ylx1NjU3NFx1NjU3MFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY0pPSSBcdTUxNmNcdTU3MTJcdTMwNmVcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGUmIzM5OzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MTY1XHU1MjliXHUzMDRiXHUzMDg5XHU0ZWU1XHU0ZTBiXHUzMDZlXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDkyXHU4YWFkXHUzMDdmXHU4ZmJjXHUzMDgxXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGNcdTY1NzRcdTY1NzAgTiwgTSxDIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY1x1NWU4M1x1NTgzNFx1MzA0YyBOIFx1NTAwYlx1ZmYwY1x1OTA1M1x1MzA0YyBNIFx1NjcyY1x1MzA0Mlx1MzA4YVx1ZmYwY1x1NTczMFx1NGUwYlx1OTA1M1x1MzA2ZVx1NjU3NFx1NTA5OVx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2Ylx1OTVhMlx1MzA1OVx1MzA4Ylx1NjU3NFx1NjU3MFx1MzA0YyBDIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgTSBcdTg4NGNcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmUgaSBcdTg4NGNcdTc2ZWUgKDEgXHUyMjY2IGkgXHUyMjY2IE0pIFx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjU3NFx1NjU3MCBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4sIEQ8c3ViPmk8XC9zdWI+IFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY1x1OTA1MyBpIFx1MzA0Y1x1NWU4M1x1NTgzNCBBPHN1Yj5pPFwvc3ViPiBcdTMwNjhcdTVlODNcdTU4MzQgQjxzdWI+aTxcL3N1Yj4gXHUzMDkyXHU3ZTRiXHUzMDRlXHVmZjBjXHU5NTc3XHUzMDU1XHUzMDRjIEQ8c3ViPmk8XC9zdWI+IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NTE2NVx1NTI5Ylx1MzBjN1x1MzBmY1x1MzBiZlx1MzA2Zlx1NGVlNVx1NGUwYlx1MzA2ZVx1Njc2MVx1NGVmNlx1MzA5Mlx1NmU4MFx1MzA1Zlx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjIgXHUyMjY2IE4gXHUyMjY2IDEwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgTSBcdTIyNjYgMjAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBDIFx1MjI2NiAxMDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IEE8c3ViPmk8XC9zdWI+IFx1MjI2NiBOICgxIFx1MjI2NiBpIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBCPHN1Yj5pPFwvc3ViPiBcdTIyNjYgTiAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+QTxzdWI+aTxcL3N1Yj4gJm5lOyBCPHN1Yj5pPFwvc3ViPiAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+KEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPikgJm5lOyAoQTxzdWI+ajxcL3N1Yj4sIEI8c3ViPmo8XC9zdWI+KSBcdTMwNGFcdTMwODhcdTMwNzMgKEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPikgJm5lOyAoQjxzdWI+ajxcL3N1Yj4sIEE8c3ViPmo8XC9zdWI+KSAoMSBcdTIyNjYgaSAmbHQ7IGogXHUyMjY2IE0pXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IEQ8c3ViPmk8XC9zdWI+IFx1MjI2NiAxMDAgMDAwICgxIFx1MjI2NiBpIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdTUxNjVcdTUyOWJcdTMwYzdcdTMwZmNcdTMwYmZcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdTMwNmZcdWZmMGNcdTMwNjlcdTMwNmVcdTVlODNcdTU4MzRcdTMwNGJcdTMwODlcdTMwNjlcdTMwNmVcdTVlODNcdTU4MzRcdTMwNzhcdTMwODJcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdTkwNTNcdTMwOTJcdThmYmZcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwODhcdTMwOGFcdTg4NGNcdTMwNTFcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTRmZGRcdThhM2NcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY0pPSSBcdTUxNmNcdTU3MTJcdTMwNmVcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHA+XHUzMDUzXHUzMDZlXHU1MTY1XHU1MjliXHU0ZjhiXHUzMDY3XHUzMDZmXHVmZjBjWCA9IDMgXHUzMDY4XHUzMDU3XHUzMDY2XHVmZjBjXHU1ZTgzXHU1ODM0IDEgXHUzMDRiXHUzMDg5XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDRjIDMgXHU0ZWU1XHU0ZTBiXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDg4XHUzMDQ2XHUzMDZhXHU1ZTgzXHU1ODM0IChcdTVlODNcdTU4MzQgMSwgXHU1ZTgzXHU1ODM0IDIsIFx1NWU4M1x1NTgzNCAzKSBcdTMwNjlcdTMwNDZcdTMwNTdcdTMwOTJcdTMwNTlcdTMwNzlcdTMwNjZcdTc2ZjhcdTRlOTJcdTMwNmJcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNjdcdTdkNTBcdTMwOTNcdTMwNjBcdTMwNjhcdTMwNGRcdWZmMGNcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNmYgMiAmdGltZXM7IDMgKyAzICsgNSA9IDE0IFx1MzA2OFx1MzA2YVx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA0Y1x1NjcwMFx1NWMwZlx1NTAyNFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2015 3번