시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB429937322.741%

문제

개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 보면 연꽃잎의 위치를 2차원 평면 위의 점으로 나타낼 수 있다. 왕눈이는 축에 평행한 직선으로만, 또 양의 방향으로만 뛸 수 있다. 따라서 왕눈이가 (x1,y1)에서 (x2,y2)로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야 한다.

  • x2 > x1 이고 y2 = y1
  • y2 > y1 이고 x2 = x1

왕눈이가 한 번 뛰는데는 K만큼의 힘이 든다. 만약 왕눈이의 힘이 K보다 작다면 더 이상 뛸 수 없다. 왕눈이는 처음에 1번 연꽃잎에 있고, N번 연꽃잎으로 이동하려고 한다. 맨 처음에 왕눈이가 가진 힘은 0이다.

각 연꽃잎에는 파리가 산다. 왕눈이는 연꽃잎에 사는 파리를 먹을 수 있다. 1마리의 파리를 먹을 때 마다 왕눈이는 1의 힘을 회복한다. 처음에 왕눈이의 힘이 0이므로 왕눈이가 뛰기 위해서는 1번 연꽃잎에 사는 파리를 먹어 힘을 얻어야 한다는 점에 주의하자.

당신은 왕눈이가 도착하고 난 뒤 가질 수 있는 힘의 최댓값을 구해야 한다. 더불어, 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램 또한 작성해야 한다.

입력

첫 줄에 연꽃잎의 수 N과 한 번 이동하는데 필요한 힘 K가 주어진다. (2 ≤ N ≤ 300 000, 1 ≤ K ≤ 1000)

다음 N개의 줄에 걸쳐 각 연꽃잎의 좌표 X, Y와 파리의 양 F가 차례대로 주어진다. i+1번째 줄에 주어지는 좌표와 파리의 양은 i번 연꽃잎에 관한 정보이다. 연꽃잎의 좌표는 서로 다르다. (0 ≤ X, Y ≤ 100 000, 0 ≤ F ≤ 1000)

입력은 항상 답이 존재하도록 주어진다.

출력

첫 줄에 N번 연꽃잎에 도착 한 뒤 최대 힘의 양을 출력한다.

두 번째 줄에는 1번 연꽃잎과 N번 연꽃잎을 포함하여 방문한 연꽃잎의 수 L을 출력한다.

다음 L개의 줄에 방문한 연꽃잎의 좌표들을 차례대로 출력한다.

만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.

예제 입력 1

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

예제 출력 1

5
4
1 1
2 1
2 3
3 3

예제 입력 2

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

예제 출력 2

36
5
1 1
1 2
2 2
3 2
3 3

예제 입력 3

9 5
5 5 10
6 5 2
7 5 1
5 6 2
6 6 6
7 6 2
5 7 1
6 7 2
7 7 1

예제 출력 3

2
3
5 5
7 5
7 7
W3sicHJvYmxlbV9pZCI6IjI5ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWJhYmJcdWM1ZDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzVmMFx1YmFiYlx1Yzc0NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHViY2Y0XHViYTc0IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgMlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzQgXHVjNzA0XHVjNzU4IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjXHViOWNjLCBcdWI2MTAgXHVjNTkxXHVjNzU4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1Y1x1YjljYyBcdWI2ZjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzY1NVx1YjIwOFx1Yzc3NFx1YWMwMCAoeDxzdWI+MTxcL3N1Yj4seTxzdWI+MTxcL3N1Yj4pXHVjNWQwXHVjMTFjICh4PHN1Yj4yPFwvc3ViPix5PHN1Yj4yPFwvc3ViPilcdWI4NWMgXHViNmYwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM1NDRcdWI3OTggXHViNDUwIFx1Yzg3MFx1YWM3NCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+eDxzdWI+MjxcL3N1Yj4gJmd0OyB4PHN1Yj4xPFwvc3ViPiBcdWM3NzRcdWFjZTAgeTxzdWI+MjxcL3N1Yj4gPSB5PHN1Yj4xPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT55PHN1Yj4yPFwvc3ViPiAmZ3Q7IHk8c3ViPjE8XC9zdWI+IFx1Yzc3NFx1YWNlMCB4PHN1Yj4yPFwvc3ViPiA9IHg8c3ViPjE8XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjU1XHViMjA4XHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWJjODggXHViNmYwXHViMjk0XHViMzcwXHViMjk0IEtcdWI5Y2NcdWQwN2NcdWM3NTggXHVkNzk4XHVjNzc0IFx1YjRlMFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzY1NVx1YjIwOFx1Yzc3NFx1Yzc1OCBcdWQ3OThcdWM3NzQgS1x1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTRcdWJhNzQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWI2ZjggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMCAxXHViYzg4IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1YzVkMCBcdWM3ODhcdWFjZTAsIE5cdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuICBcdWI5ZTggXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzY1NVx1YjIwOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzQgXHVkNzk4XHVjNzQwIDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM1ZDBcdWIyOTQgXHVkMzBjXHViOWFjXHVhYzAwIFx1YzBiMFx1YjJlNC4gXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1YzVkMCBcdWMwYWNcdWIyOTQgXHVkMzBjXHViOWFjXHViOTdjIFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiAxXHViOWM4XHViOWFjXHVjNzU4IFx1ZDMwY1x1YjlhY1x1Yjk3YyBcdWJhMzlcdWM3NDQgXHViNTRjIFx1YjljOFx1YjJlNCBcdWM2NTVcdWIyMDhcdWM3NzRcdWIyOTQgMVx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVkNjhjXHViY2Y1XHVkNTVjXHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjNjU1XHViMjA4XHVjNzc0XHVjNzU4IFx1ZDc5OFx1Yzc3NCAwXHVjNzc0XHViYmMwXHViODVjIFx1YzY1NVx1YjIwOFx1Yzc3NFx1YWMwMCBcdWI2ZjBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IDFcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwIFx1YzBhY1x1YjI5NCBcdWQzMGNcdWI5YWNcdWI5N2MgXHViYTM5XHVjNWI0IFx1ZDc5OFx1Yzc0NCBcdWM1YmJcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0XHViMjk0IFx1YzgxMFx1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NThcdWM3OTAuIDxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjNjU1XHViMjA4XHVjNzc0XHVhYzAwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViNGE0IFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDc5OFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMzU0XHViZDg4XHVjNWI0LCBcdWM1ZjBcdWFmNDNcdWM3OGUgXHVjMGFjXHVjNzc0XHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWI2MTBcdWQ1NWMgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1ZDU1YyBcdWJjODggXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDMwMCAwMDAsIDEgJmxlOyBLICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDEgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBYLCBZXHVjNjQwIFx1ZDMwY1x1YjlhY1x1Yzc1OCBcdWM1OTEgRlx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVkMzBjXHViOWFjXHVjNzU4IFx1YzU5MVx1Yzc0MCBpXHViYzg4IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1YzVkMCBcdWFkMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVjNzc0XHViMmU0LiBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuICgwICZsZTsgWCwgWSAmbGU7IDEwMCAwMDAsIDAgJmxlOyBGICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIE5cdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwIFx1YjNjNFx1Y2MyOSBcdWQ1NWMgXHViNGE0IFx1Y2Q1Y1x1YjMwMCBcdWQ3OThcdWM3NTggXHVjNTkxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWFjZmMgTlx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NTggXHVjMjE4IExcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTVjIFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI0ZTRcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJBUklDQSIsImRlc2NyaXB0aW9uIjoiPHA+QmFyaWNhIGlzIGFuIHVudXN1YWwgZnJvZy4gU2hlIGxpdmVzIGluIGEgcG9uZCB3aGVyZSBOIHBsYW50cyBmbG9hdCBvbiB0aGUgc3VyZmFjZSBvZiB0aGUgd2F0ZXIuIFRoZSBwbGFudHMgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBOLiBXaGVuIHZpZXdpbmcgZnJvbSBhYm92ZSwgdGhlIGxvY2F0aW9uIG9mIGVhY2ggcGxhbnQgaXMgZ2l2ZW4gYnkgYSBwYWlyIG9mIGNvb3JkaW5hdGVzLiBXaGF0IG1ha2VzIEJhcmljYSB1bnVzdWFsIGlzIGhlciBmZWFyIG9mIGp1bXBpbmcgZGlhZ29uYWxseSBhbmQgaW4gdGhlIG5lZ2F0aXZlIGRpcmVjdGlvbi4gTW9yZSBwcmVjaXNlbHksIHNoZSBjYW4ganVtcCBmcm9tIGEgcGxhbnQgYXQgY29vcmRpbmF0ZXMgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPikgdG8gYW5vdGhlciBhdCBjb29yZGluYXRlcyAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSBvbmx5IGlmOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPng8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj4gYW5kIHk8c3ViPjI8XC9zdWI+ID0geTxzdWI+MTxcL3N1Yj4sIG9yJm5ic3A7PFwvbGk+XHJcblx0PGxpPnk8c3ViPjI8XC9zdWI+ICZndDsgeTxzdWI+MTxcL3N1Yj4gYW5kIHg8c3ViPjI8XC9zdWI+ID0geDxzdWI+MTxcL3N1Yj48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZWFjaCBwbGFudCwgd2Uga25vdyB0aGUgbnVtYmVyIG9mIGZsaWVzIGluIGl0cyBpbW1lZGlhdGUgdmljaW5pdHkuIEJhcmljYSBjYW4gdXNlIGhlciBzd2lmdCB0b25ndWUgdG8gZWF0IGFsbCBmbGllcyBuZWFyIHRoZSBwbGFudCBzaGUgaXMgYXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJhcmljYSBhYnNvcmJzIG9uZSBlbmVyZ3kgdW5pdCBmb3IgZWFjaCBmbHkgc2hlIGVhdHMsIGFuZCB1c2VzIEsgZW5lcmd5IHVuaXRzIGZvciBlYWNoIGp1bXAgc2hlIG1ha2VzLiBCYXJpY2EgY2FuIG5vdCBtYWtlIGEganVtcCBpZiBzaGUgZG9lc24mIzM5O3QgaGF2ZSBlbm91Z2ggZW5lcmd5IHVuaXRzIGJlZm9yZWhhbmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJhcmljYSB3YW50cyB0byBnbyBmcm9tIHBsYW50IDEgdG8gcGxhbnQgTiBhbmQgaGF2ZSB0aGUgbGFyZ2VzdCBhbW91bnQgb2YgZW5lcmd5IHBvc3NpYmxlIGFmdGVyIGFycml2aW5nLiBCYXJpY2EgaW5pdGlhbGx5IGhhcyBubyBlbmVyZ3kgYW5kIG11c3QgZ2F0aGVyIGVuZXJneSBmb3IgaGVyIGZpcnN0IGp1bXAgZnJvbSB0aGUgZmxpZXMgYXJvdW5kIHBsYW50IDEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIHNlcXVlbmNlIG9mIHBsYW50cyBCYXJpY2Egc2hvdWxkIHRyYXZlbCB0byBhY2hpZXZlIGhlciBnb2FsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwKSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgWCwgWSBhbmQgRiAoMCAmbGU7IFgsIFkgJmxlOyAxMDAgMDAwLCAwICZsZTsgRiAmbGU7IDEwMDApIHNlcGFyYXRlZCBieSBzcGFjZXMsIG1lYW5pbmcgdGhhdCB0aGVyZSBpcyBhIHBsYW50IGF0IGNvb3JkaW5hdGVzIChYLCBZKSB3aXRoIEYgZmxpZXMgYXJvdW5kIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgcGxhbnQgaW4gdGhlIGlucHV0IGlzIHBsYW50IDEsIHRoZSBzZWNvbmQgaXMgcGxhbnQgMiBldGMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byBwbGFudHMgd2lsbCBzaGFyZSB0aGUgc2FtZSBwYWlyIG9mIGNvb3JkaW5hdGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgaW5wdXQgZGF0YSB3aWxsIGd1YXJhbnRlZSB0aGF0IGEgc2VxdWVuY2Ugb2YganVtcHMsIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgZmluYWwgZW5lcmd5IGxldmVsIG9uIHRoZSBmaXJzdCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdXRwdXQgYW4gaW50ZWdlciBMLCB0aGUgbnVtYmVyIG9mIHBsYW50cyBCYXJpY2Egc2hvdWxkIHRyYXZlbCwgaW5jbHVkaW5nIHBsYW50cyAxIGFuZCBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgZm9sbG93aW5nIEwgbGluZXMsIG91dHB1dCB0aGUgc2VxdWVuY2Ugb2YgcGxhbnRzIEJhcmljYSBzaG91bGQgdHJhdmVsLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #5 5번