시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB52824420648.244%

문제

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라는 것을 의미한다.

출력

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

제한

  • 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).
  • 어떤 광장에서도 한 개 이상의 도로를 통해서 다른 광장으로 갈 수 있다.

서브태스크 1 (15점)

  • N ≦ 100.
  • M ≦ 200.
  • C ≦ 100.
  • Di ≦ 10 (1 ≦ i ≦ M).

서브태스크 2 (45점)

  • N ≦ 100.
  • M ≦ 4 000.

서브태스크 3 (40점)

추가적인 제약 조건이 없다.

예제 입력 1

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

예제 출력 1

14

이 입력 예제에서는 X = 3으로 하여 광장 1로부터 거리가 3이하가 되는 광장(광장 1, 광장 2, 광장 3)을 전부 지하도로 이었을 경우, 정비하는 데에 드는 비용의 합은 (2 × 3) + (3 + 5) = 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
W3sicHJvYmxlbV9pZCI6IjEwNzE1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSk9JIFx1YWNmNVx1YzZkMCIsImRlc2NyaXB0aW9uIjoiPHA+MjBYWFx1YjE0NFx1YzVkMCBJT0lcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWMgXHVjNWY0XHViOWFjXHViMjk0IFx1YzYyY1x1YjliY1x1ZDUzZCBcdWM5MDBcdWJlNDRcdWM3NTggXHVjNzdjXHVkNjU4XHVjNzNjXHViODVjIElPSVx1YjA5OFx1Yjc3Y1x1YzVkMCBcdWM3ODhcdWIyOTQgSk9JXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzgxNVx1YmU0NFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIEpPSVx1YWNmNVx1YzZkMFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YWQxMVx1YzdhNVx1Yzc3NCBcdWM3ODhcdWFjZTAsIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjZjVcdWM2ZDBcdWM1ZDBcdWIyOTQgXHVhZDExXHVjN2E1XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIDFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMmU0LiBcdWIzYzRcdWI4NWMgaSAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWIyOTQgXHVhZDExXHVjN2E1IEFpXHVjNjQwIFx1YWQxMVx1YzdhNSBCaVx1Yjk3YyBcdWMzMGRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwIFx1YWRmOCBcdWFlMzhcdWM3NzRcdWIyOTQgRGlcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWFkMTFcdWM3YTVcdWM1ZDBcdWMxMWNcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWIyZTRcdWI5NzggXHVhZDExXHVjN2E1XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWJlNDRcdWFjYzRcdWQ2OGRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjOWMwXHVkNTU4XHViM2M0IFx1YzEyNFx1Y2U1OFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViY2MwXHVjMjE4IENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhM2NcdWM4MDAsIDAgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxNVx1YzIxOCBYXHViOTdjIFx1YWNlMFx1Yjk3NFx1YWNlMCBcdWFkMTFcdWM3YTUgMVx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFjNzBcdWI5YWNcdWFjMDAgWFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWFkMTFcdWM3YTUoXHVhZDExXHVjN2E1IDFcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjKSBcdWJhYThcdWI0NTBcdWI5N2MgXHVjOWMwXHVkNTU4XHViM2M0XHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWFkMTFcdWM3YTUgaVx1YzY0MCBcdWFkMTFcdWM3YTUgalx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVhZDExXHVjN2E1IGlcdWI4NWNcdWJkODBcdWQxMzAgXHVhZDExXHVjN2E1IGpcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWM5YzBcdWQ1NThcdWIzYzRcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTU4XHViMjk0IFx1YjM3MFx1YzVkMCBcdWI0ZGNcdWIyOTQgXHVjODA0XHVjY2I0IFx1YmU0NFx1YzZhOVx1Yzc0MCBDICZ0aW1lczsgWFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNzNjXHViODVjLCBcdWM5YzBcdWQ1NThcdWIzYzRcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWQxMVx1YzdhNVx1YjRlNFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1YzgwNFx1YmQ4MCBcdWNjYTBcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWNjYTBcdWFjNzBcdWQ1NThcdWIyOTQgXHViMzcwXHVjNWQwIFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFx1Y2NhMFx1YWM3MFx1YjQxOFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMGE4XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM4MDRcdWJkODAgXHViY2Y0XHVjMjE4XHVkNTVjXHViMmU0LiBcdWFlMzhcdWM3NzQgZFx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViY2Y0XHVjMjE4XHVkNTU4XHViMjk0XHViMzcwXHVjNWQwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViZTQ0XHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzJlNFx1YzJkY1x1ZDU1OFx1YWUzMCBcdWM4MDQsIEpPSVx1YWNmNVx1YzZkMFx1YzVkMCBcdWM5YzBcdWQ1NThcdWIzYzRcdWIyOTQgXHVjNWM2XHViMmU0LiBKT0lcdWFjZjVcdWM2ZDBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQxMVx1YzdhNVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVjOWMwXHVkNTU4XHViM2M0IFx1YzEyNFx1Y2U1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgSk9JXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzgxNVx1YmU0NFx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViMmU0XHVjNzRjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IE4sIE0sIENcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWFkMTFcdWM3YTVcdWM3NzQgTlx1YWMxYywgXHViM2M0XHViODVjXHVhYzAwIE1cdWFjMWMgXHVjNzg4XHVhY2UwLCBcdWM5YzBcdWQ1NThcdWIzYzQgXHVjMTI0XHVjZTU4XHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWJjYzBcdWMyMThcdWFjMDAgQ1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWQ1ODlcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjODE1XHVjMjE4IEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiwgRDxzdWI+aTxcL3N1Yj4gKDEgXHUyMjY2IGkgXHUyMjY2IE0pIFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1ZDU1YyBcdWM5MDRcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NDAgXHViM2M0XHViODVjIGlcdWFjMDAgXHVhZDExXHVjN2E1IEE8c3ViPmk8XC9zdWI+XHVjNjQwIEI8c3ViPmk8XC9zdWI+XHViOTdjIFx1Yzc4N1x1YWNlMCwgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YWMwMCBEPHN1Yj5pPFwvc3ViPlx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Sk9JXHVhY2Y1XHVjNmQwIFx1YzgxNVx1YmU0NFx1YzVkMCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCAxXHVjOTA0XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MiBcdTIyNjYgTiBcdTIyNjYgMTAwIDAwMC48XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgTSBcdTIyNjYgMjAwIDAwMC48XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgQyBcdTIyNjYgMTAwIDAwMC48XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgQTxzdWI+aTxcL3N1Yj4gXHUyMjY2IE4gKDEgXHUyMjY2IGkgXHUyMjY2IE0pLjxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBCPHN1Yj5pPFwvc3ViPiBcdTIyNjYgTiAoMSBcdTIyNjYgaSBcdTIyNjYgTSkuPFwvbGk+XHJcblx0PGxpPkE8c3ViPmk8XC9zdWI+ICZuZTsgQjxzdWI+aTxcL3N1Yj4gKDEgXHUyMjY2IGkgXHUyMjY2IE0pLjxcL2xpPlxyXG5cdDxsaT4oQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+KSAmbmU7IChBPHN1Yj5qPFwvc3ViPiwgQjxzdWI+ajxcL3N1Yj4pIFx1YmMwZiAoQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+KSAmbmU7IChCPHN1Yj5qPFwvc3ViPiwgQTxzdWI+ajxcL3N1Yj4pICgxIFx1MjI2NiBpICZsdDsgaiBcdTIyNjYgTSkuPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IEQ8c3ViPmk8XC9zdWI+IFx1MjI2NiAxMDAgMDAwICgxIFx1MjI2NiBpIFx1MjI2NiBNKS48XC9saT5cclxuXHQ8bGk+XHVjNWI0XHViNWE0IFx1YWQxMVx1YzdhNVx1YzVkMFx1YzExY1x1YjNjNCBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWFkMTFcdWM3YTVcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+TiBcdTIyNjYgMTAwLjxcL2xpPlxyXG5cdDxsaT5NIFx1MjI2NiAyMDAuPFwvbGk+XHJcblx0PGxpPkMgXHUyMjY2IDEwMC48XC9saT5cclxuXHQ8bGk+RDxzdWI+aTxcL3N1Yj4gXHUyMjY2IDEwICgxIFx1MjI2NiBpIFx1MjI2NiBNKS48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT5OIFx1MjI2NiAxMDAuPFwvbGk+XHJcblx0PGxpPk0gXHUyMjY2IDQgMDAwLjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1Yzc3NCBcdWM3ODVcdWI4MjUgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFggPSAzXHVjNzNjXHViODVjIFx1ZDU1OFx1YzVlYyBcdWFkMTFcdWM3YTUgMVx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWFjNzBcdWI5YWNcdWFjMDAgM1x1Yzc3NFx1ZDU1OFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhZDExXHVjN2E1KFx1YWQxMVx1YzdhNSAxLCBcdWFkMTFcdWM3YTUgMiwgXHVhZDExXHVjN2E1IDMpXHVjNzQ0IFx1YzgwNFx1YmQ4MCBcdWM5YzBcdWQ1NThcdWIzYzRcdWI4NWMgXHVjNzc0XHVjNWM4XHVjNzQ0IFx1YWNiZFx1YzZiMCwgXHVjODE1XHViZTQ0XHVkNTU4XHViMjk0IFx1YjM3MFx1YzVkMCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1ZDU2OVx1Yzc0MCAoMiAmdGltZXM7IDMpICsgKDMgKyA1KSA9IDE0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NzQgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjEwNzE1IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JIFx1NTE2Y1x1NTcxMiAoSk9JIFBhcmspIiwiZGVzY3JpcHRpb24iOiI8cD4yMFhYIFx1NWU3NFx1MzA2YiBJT0kgXHU1NmZkXHUzMDY3XHU4ODRjXHUzMDhmXHUzMDhjXHUzMDhiXHUzMGFhXHUzMGVhXHUzMGYzXHUzMGQ0XHUzMGMzXHUzMGFmXHUzMDZiXHU1MDk5XHUzMDQ4XHVmZjBjSU9JIFx1NTZmZFx1MzA2Ylx1MzA0Mlx1MzA4YiBKT0kgXHU1MTZjXHU1NzEyXHUzMDkyXHU2NTc0XHU1MDk5XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDZhXHUzMDYzXHUzMDVmXHVmZjBlSk9JXHU1MTZjXHU1NzEyXHUzMDZiXHUzMDZmIE4gXHU1MDBiXHUzMDZlXHU1ZTgzXHU1ODM0XHUzMDRjXHUzMDQyXHUzMDhhXHVmZjBjXHU1ZTgzXHU1ODM0XHUzMDZiXHUzMDZmIDEgXHUzMDRiXHUzMDg5IE4gXHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDRjXHUzMDY0XHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU1ZTgzXHU1ODM0XHUzMDkyXHU3ZTRiXHUzMDUwIE0gXHU2NzJjXHUzMDZlXHU5MDUzXHUzMDRjXHUzMDQyXHUzMDhhXHVmZjBjXHU5MDUzXHUzMDZiXHUzMDZmIDEgXHUzMDRiXHUzMDg5IE0gXHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDRjXHUzMDY0XHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU5MDUzIGkgKDEgXHUyMjY2IGkgXHUyMjY2IE0pIFx1MzA2Zlx1NWU4M1x1NTgzNCBBaSBcdTMwNjhcdTVlODNcdTU4MzQgQmkgXHUzMDkyXHU1M2NjXHU2NWI5XHU1NDExXHUzMDZiXHU3ZTRiXHUzMDQ0XHUzMDY3XHUzMDRhXHUzMDhhXHVmZjBjXHU5NTc3XHUzMDU1XHUzMDZmIERpIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1MzA2OVx1MzA2ZVx1NWU4M1x1NTgzNFx1MzA0Ylx1MzA4OVx1MzA2OVx1MzA2ZVx1NWU4M1x1NTgzNFx1MzA3OFx1MzA4Mlx1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1OTA1M1x1MzA5Mlx1OGZiZlx1MzA2M1x1MzA2Nlx1ODg0Y1x1MzA0Zlx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTY1NzRcdTUwOTlcdThhMDhcdTc1M2JcdTMwNjdcdTMwNmZcdWZmMGNcdTMwN2VcdTMwNWFcdWZmMGMwIFx1NGVlNVx1NGUwYVx1MzA2ZVx1NjU3NFx1NjU3MCBYIFx1MzA5Mlx1OTA3OFx1MzA3M1x1ZmYwY1x1NWU4M1x1NTgzNCAxIFx1MzA0Ylx1MzA4OVx1MzA2ZVx1OGRkZFx1OTZlMlx1MzA0YyBYIFx1NGVlNVx1NGUwYlx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA4OFx1MzA0Nlx1MzA2YVx1NWU4M1x1NTgzNCAoXHU1ZTgzXHU1ODM0IDEgXHUzMDkyXHU1NDJiXHUzMDgwKSBcdTMwNjlcdTMwNDZcdTMwNTdcdTMwOTJcdTMwNTlcdTMwNzlcdTMwNjZcdTc2ZjhcdTRlOTJcdTMwNmJcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNjdcdTdkNTBcdTMwNzZcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTVlODNcdTU4MzQgaSBcdTMwNjhcdTVlODNcdTU4MzQgaiBcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNjhcdTMwNmZcdWZmMGNcdTVlODNcdTU4MzQgaSBcdTMwNGJcdTMwODlcdTVlODNcdTU4MzQgaiBcdTMwNmJcdTg4NGNcdTMwNGZcdTMwNjhcdTMwNGRcdTMwNmJcdTkwMWFcdTMwOGJcdTkwNTNcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmVcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTY1NzRcdTUwOTlcdThhMDhcdTc1M2JcdTMwNjdcdTMwNmZcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNmVcdTY1NzRcdTUwOTlcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmJcdTk1YTJcdTMwNTlcdTMwOGJcdTY1NzRcdTY1NzAgQyBcdTMwNGNcdTViOWFcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNmVcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmYgQyAmdGltZXM7IFggXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NmIyMVx1MzA2Ylx1ZmYwY1x1NTczMFx1NGUwYlx1OTA1M1x1MzA2N1x1N2Q1MFx1MzA3MFx1MzA4Y1x1MzA1Zlx1NWU4M1x1NTgzNFx1MzA2OVx1MzA0Nlx1MzA1N1x1MzA5Mlx1N2Q1MFx1MzA3Nlx1OTA1M1x1MzA5Mlx1MzA1OVx1MzA3OVx1MzA2Nlx1NjRhNFx1NTNiYlx1MzA1OVx1MzA4Ylx1ZmYwZVx1OTA1M1x1MzA2ZVx1NjRhNFx1NTNiYlx1MzA2Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2Zlx1MzA0Ylx1MzA0Ylx1MzA4OVx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTY3MDBcdTVmOGNcdTMwNmJcdWZmMGNcdTY0YTRcdTUzYmJcdTMwNTVcdTMwOGNcdTMwNWFcdTMwNmJcdTZiOGJcdTMwNjNcdTMwNWZcdTkwNTNcdTMwOTJcdTMwNTlcdTMwNzlcdTMwNjZcdTg4ZGNcdTRmZWVcdTMwNTlcdTMwOGJcdWZmMGVcdTk1NzdcdTMwNTUgZCBcdTMwNmVcdTkwNTNcdTMwOTJcdTg4ZGNcdTRmZWVcdTMwNTlcdTMwOGJcdTMwNWZcdTMwODFcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmYgZCBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU2NTc0XHU1MDk5XHU4YTA4XHU3NTNiXHU1YjlmXHU2NWJkXHU1MjRkXHUzMDZlIEpPSSBcdTUxNmNcdTU3MTJcdTMwNmJcdTMwNmZcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGVKT0kgXHU1MTZjXHU1NzEyXHUzMDZlXHU2NTc0XHU1MDk5XHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZlXHU1NDhjXHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwPkpPSSBcdTUxNmNcdTU3MTJcdTMwNmVcdTVlODNcdTU4MzRcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNjhcdWZmMGNcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNmVcdTY1NzRcdTUwOTlcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmJcdTk1YTJcdTMwNTlcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNKT0kgXHU1MTZjXHU1NzEyXHUzMDZlXHU2NTc0XHU1MDk5XHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZlXHU1NDhjXHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlJiMzOTs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHVmZjBjXHU2NTc0XHU2NTcwIE4sIE0sQyBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNcdTVlODNcdTU4MzRcdTMwNGMgTiBcdTUwMGJcdWZmMGNcdTkwNTNcdTMwNGMgTSBcdTY3MmNcdTMwNDJcdTMwOGFcdWZmMGNcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNmVcdTY1NzRcdTUwOTlcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmJcdTk1YTJcdTMwNTlcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNGMgQyBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU3ZDlhXHUzMDRmIE0gXHU4ODRjXHUzMDZlXHUzMDQ2XHUzMDYxXHUzMDZlIGkgXHU4ODRjXHU3NmVlICgxIFx1MjI2NiBpIFx1MjI2NiBNKSBcdTMwNmJcdTMwNmZcdWZmMGNcdTY1NzRcdTY1NzAgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+LCBEPHN1Yj5pPFwvc3ViPiBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNcdTkwNTMgaSBcdTMwNGNcdTVlODNcdTU4MzQgQTxzdWI+aTxcL3N1Yj4gXHUzMDY4XHU1ZTgzXHU1ODM0IEI8c3ViPmk8XC9zdWI+IFx1MzA5Mlx1N2U0Ylx1MzA0ZVx1ZmYwY1x1OTU3N1x1MzA1NVx1MzA0YyBEPHN1Yj5pPFwvc3ViPiBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY0pPSSBcdTUxNmNcdTU3MTJcdTMwNmVcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4yIFx1MjI2NiBOIFx1MjI2NiAxMDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IE0gXHUyMjY2IDIwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgQyBcdTIyNjYgMTAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBBPHN1Yj5pPFwvc3ViPiBcdTIyNjYgTiAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+MSBcdTIyNjYgQjxzdWI+aTxcL3N1Yj4gXHUyMjY2IE4gKDEgXHUyMjY2IGkgXHUyMjY2IE0pXHVmZjBlPFwvbGk+XHJcblx0PGxpPkE8c3ViPmk8XC9zdWI+ICZuZTsgQjxzdWI+aTxcL3N1Yj4gKDEgXHUyMjY2IGkgXHUyMjY2IE0pXHVmZjBlPFwvbGk+XHJcblx0PGxpPihBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4pICZuZTsgKEE8c3ViPmo8XC9zdWI+LCBCPHN1Yj5qPFwvc3ViPikgXHUzMDRhXHUzMDg4XHUzMDczIChBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4pICZuZTsgKEI8c3ViPmo8XC9zdWI+LCBBPHN1Yj5qPFwvc3ViPikgKDEgXHUyMjY2IGkgJmx0OyBqIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBEPHN1Yj5pPFwvc3ViPiBcdTIyNjYgMTAwIDAwMCAoMSBcdTIyNjYgaSBcdTIyNjYgTSlcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU1MTY1XHU1MjliXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHUzMDZmXHVmZjBjXHUzMDY5XHUzMDZlXHU1ZTgzXHU1ODM0XHUzMDRiXHUzMDg5XHUzMDY5XHUzMDZlXHU1ZTgzXHU1ODM0XHUzMDc4XHUzMDgyXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU5MDUzXHUzMDkyXHU4ZmJmXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDg4XHUzMDhhXHU4ODRjXHUzMDUxXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHU0ZmRkXHU4YTNjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+TiBcdTIyNjYgMTAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPk0gXHUyMjY2IDIwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5DIFx1MjI2NiAxMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+RDxzdWI+aTxcL3N1Yj4gXHUyMjY2IDEwICgxIFx1MjI2NiBpIFx1MjI2NiBNKVx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8dWw+XHJcblx0PGxpPk4gXHUyMjY2IDEwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5NIFx1MjI2NiA0IDAwMFx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8cD5cdThmZmRcdTUyYTBcdTMwNmVcdTUyMzZcdTk2NTBcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHUzMDUzXHUzMDZlXHU1MTY1XHU1MjliXHU0ZjhiXHUzMDY3XHUzMDZmXHVmZjBjWCA9IDMgXHUzMDY4XHUzMDU3XHUzMDY2XHVmZjBjXHU1ZTgzXHU1ODM0IDEgXHUzMDRiXHUzMDg5XHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDRjIDMgXHU0ZWU1XHU0ZTBiXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDg4XHUzMDQ2XHUzMDZhXHU1ZTgzXHU1ODM0IChcdTVlODNcdTU4MzQgMSwgXHU1ZTgzXHU1ODM0IDIsIFx1NWU4M1x1NTgzNCAzKSBcdTMwNjkgXHUzMDQ2XHUzMDU3XHUzMDkyXHUzMDU5XHUzMDc5XHUzMDY2XHU3NmY4XHU0ZTkyXHUzMDZiXHU1NzMwXHU0ZTBiXHU5MDUzXHUzMDY3XHU3ZDUwXHUzMDkzXHUzMDYwXHUzMDY4XHUzMDRkXHVmZjBjXHU2NTc0XHU1MDk5XHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHUzMGIzXHUzMGI5XHUzMGM4XHUzMDZlXHU1NDhjXHUzMDZmIDIgJnRpbWVzOyAzICsgMyArIDUgPSAxNCBcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNGNcdTY3MDAgXHU1YzBmXHU1MDI0XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1MzA1M1x1MzA2ZVx1NTE2NVx1NTI5Ylx1NGY4Ylx1MzA2N1x1MzA2Zlx1ZmYwY1ggPSAwIFx1MzA2ZVx1MzA2OFx1MzA0ZFx1NjU3NFx1NTA5OVx1MzA2Ylx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzBiM1x1MzBiOVx1MzBjOFx1MzA2ZVx1NTQ4Y1x1MzA0Y1x1NjcwMFx1NWMwZlx1MzA2Ylx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD5cdTMwNTNcdTMwNmVcdTUxNjVcdTUyOWJcdTRmOGJcdTMwNjdcdTMwNmZcdWZmMGNYID0gNSBcdTMwNjhcdTMwNTdcdTMwNjZcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTVlODNcdTU4MzRcdTMwOTJcdTc2ZjhcdTRlOTJcdTMwNmJcdTU3MzBcdTRlMGJcdTkwNTNcdTMwNjdcdTdkNTBcdTMwOTNcdTMwNjBcdTMwNjhcdTMwNGRcdWZmMGNcdTY1NzRcdTUwOTlcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTMwYjNcdTMwYjlcdTMwYzhcdTMwNmVcdTU0OGNcdTMwNGMgXHU2NzAwXHU1YzBmXHUzMDZiXHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIn1d

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2014/2015 3번

채점 및 기타 정보

  • 예제는 채점하지 않는다.