시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 347 67 49 20.332%

문제

개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 봤을 때 2차원 평면에 연꽃잎이 (x,y) 좌표에 떠 있는 것 처럼 보인다. 왕눈이는 대각선으로 뛰는 것과 음의 방향으로 뛰는 것을 무서워 한다. 좀 더 자세히 말하자면 (x 1,y1)에서 (x2,y2)로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야한다.

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

각 연꽃잎 마다 일정 수의 파리가 있고, 왕눈이는 파리를 먹으며 힘을 회복한다.

왕눈이가 한 번 연꽃잎을 이동하기 위해서는 K 만큼 힘이 든다. 왕눈이는 처음 1번 연꽃잎에서 시작하여 N번 연꽃잎으로 이동하려고 한다. 다만, 도착하고 난 뒤 힘의 최대이고 싶어한다. 처음 왕눈이가 가진 힘은 0 이다. 힘은 항상 0 이상 이어야 한다.

왕눈이를 도와 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 연꽃잎의 수 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
W3sicHJvYmxlbV9pZCI6IjI5ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWJhYmJcdWM1ZDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzVmMFx1YmFiYlx1Yzc0NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHViZDI0XHVjNzQ0IFx1YjU0YyAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMCZuYnNwO1x1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc3NCAoeCx5KSBcdWM4OGNcdWQ0NWNcdWM1ZDAgXHViNWEwIFx1Yzc4OFx1YjI5NCBcdWFjODMgXHVjYzk4XHViN2ZjIFx1YmNmNFx1Yzc3OFx1YjJlNC4gXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1YjMwMFx1YWMwMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWI2ZjBcdWIyOTQgXHVhYzgzXHVhY2ZjIFx1Yzc0Y1x1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViNmYwXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJiMzRcdWMxMWNcdWM2Y2MgXHVkNTVjXHViMmU0LiBcdWM4ODAgXHViMzU0IFx1Yzc5MFx1YzEzOFx1ZDc4OCBcdWI5ZDBcdWQ1NThcdWM3OTBcdWJhNzQgKHggPHN1Yj4xPFwvc3ViPix5PHN1Yj4xPFwvc3ViPilcdWM1ZDBcdWMxMWMgKHg8c3ViPjI8XC9zdWI+LHk8c3ViPjI8XC9zdWI+KVx1Yjg1YyBcdWI2ZjBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzU0NFx1Yjc5OCBcdWI0NTAgXHVjODcwXHVhYzc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPng8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj4gXHVjNzc0XHVhY2UwIHk8c3ViPjI8XC9zdWI+ID0geTxzdWI+MTxcL3N1Yj48XC9saT5cclxuXHQ8bGk+eTxzdWI+MjxcL3N1Yj4gJmd0OyB5PHN1Yj4xPFwvc3ViPiBcdWM3NzRcdWFjZTAgeDxzdWI+MjxcL3N1Yj4gPSB4PHN1Yj4xPFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMSBcdWM1ZjBcdWFmNDNcdWM3OGUgXHViOWM4XHViMmU0IFx1Yzc3Y1x1YzgxNSBcdWMyMThcdWM3NTggXHVkMzBjXHViOWFjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1ZDMwY1x1YjlhY1x1Yjk3YyBcdWJhMzlcdWM3M2NcdWJhNzAgXHVkNzk4XHVjNzQ0IFx1ZDY4Y1x1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjU1XHViMjA4XHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgSyBcdWI5Y2NcdWQwN2MgXHVkNzk4XHVjNzc0Jm5ic3A7XHViNGUwXHViMmU0LiBcdWM2NTVcdWIyMDhcdWM3NzRcdWIyOTQgXHVjYzk4XHVjNzRjIDFcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBOXHViYzg4IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5Y2MsIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViNGE0IFx1ZDc5OFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWM3NzRcdWFjZTAmbmJzcDtcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1Y2M5OFx1Yzc0YyBcdWM2NTVcdWIyMDhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWM0IFx1ZDc5OFx1Yzc0MCAwIFx1Yzc3NFx1YjJlNC4gXHVkNzk4XHVjNzQwIFx1ZDU2ZFx1YzBjMSAwIFx1Yzc3NFx1YzBjMSBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2NTVcdWIyMDhcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzVmMFx1YWY0M1x1Yzc4ZSBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1ZDU1YyBcdWJjODggXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDIgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NTggXHVjODhjXHVkNDVjIFgsIFlcdWM2NDAgXHVkMzBjXHViOWFjXHVjNzU4IFx1YzU5MSBGXHVhYzAwJm5ic3A7XHVjYzI4XHViODQwXHViMzAwXHViODVjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVkMzBjXHViOWFjXHVjNzU4IFx1YzU5MVx1Yzc0MCZuYnNwO2lcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuIFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4mbmJzcDsoMCAmbGU7IFgsIFkgJmxlOyAxMDAgMDAwLCAwICZsZTsgRiAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCZuYnNwO1x1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwJm5ic3A7Tlx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM1ZDAgXHViM2M0XHVjYzI5IFx1ZDU1YyBcdWI0YTQgXHVjZDVjXHViMzAwJm5ic3A7XHVkNzk4XHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCZuYnNwO1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWFjZmMgTlx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjJm5ic3A7XHViYzI5XHViYjM4XHVkNTVjIFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWMyMTggTFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBMXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjRlNFx1Yzc0NCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjJm5ic3A7XHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWFkZjggXHVjOTExIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJBUklDQSIsImRlc2NyaXB0aW9uIjoiPHA+QmFyaWNhIGlzIGFuIHVudXN1YWwgZnJvZy4gU2hlIGxpdmVzIGluIGEgcG9uZCB3aGVyZSBOIHBsYW50cyBmbG9hdCBvbiB0aGUgc3VyZmFjZSBvZiB0aGUgd2F0ZXIuIFRoZSBwbGFudHMgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBOLiBXaGVuIHZpZXdpbmcgZnJvbSBhYm92ZSwgdGhlIGxvY2F0aW9uIG9mIGVhY2ggcGxhbnQgaXMgZ2l2ZW4gYnkgYSBwYWlyIG9mIGNvb3JkaW5hdGVzLiBXaGF0IG1ha2VzIEJhcmljYSB1bnVzdWFsIGlzIGhlciBmZWFyIG9mIGp1bXBpbmcgZGlhZ29uYWxseSBhbmQgaW4gdGhlIG5lZ2F0aXZlIGRpcmVjdGlvbi4gTW9yZSBwcmVjaXNlbHksIHNoZSBjYW4ganVtcCBmcm9tIGEgcGxhbnQgYXQgY29vcmRpbmF0ZXMgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPikgdG8gYW5vdGhlciBhdCBjb29yZGluYXRlcyAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSBvbmx5IGlmOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPng8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj4gYW5kIHk8c3ViPjI8XC9zdWI+ID0geTxzdWI+MTxcL3N1Yj4sIG9yJm5ic3A7PFwvbGk+XHJcblx0PGxpPnk8c3ViPjI8XC9zdWI+ICZndDsgeTxzdWI+MTxcL3N1Yj4gYW5kIHg8c3ViPjI8XC9zdWI+ID0geDxzdWI+MTxcL3N1Yj48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZWFjaCBwbGFudCwgd2Uga25vdyB0aGUgbnVtYmVyIG9mIGZsaWVzIGluIGl0cyBpbW1lZGlhdGUgdmljaW5pdHkuIEJhcmljYSBjYW4gdXNlIGhlciBzd2lmdCB0b25ndWUgdG8gZWF0IGFsbCBmbGllcyBuZWFyIHRoZSBwbGFudCBzaGUgaXMgYXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJhcmljYSBhYnNvcmJzIG9uZSBlbmVyZ3kgdW5pdCBmb3IgZWFjaCBmbHkgc2hlIGVhdHMsIGFuZCB1c2VzIEsgZW5lcmd5IHVuaXRzIGZvciBlYWNoIGp1bXAgc2hlIG1ha2VzLiBCYXJpY2EgY2FuIG5vdCBtYWtlIGEganVtcCBpZiBzaGUgZG9lc24mIzM5O3QgaGF2ZSBlbm91Z2ggZW5lcmd5IHVuaXRzIGJlZm9yZWhhbmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJhcmljYSB3YW50cyB0byBnbyBmcm9tIHBsYW50IDEgdG8gcGxhbnQgTiBhbmQgaGF2ZSB0aGUgbGFyZ2VzdCBhbW91bnQgb2YgZW5lcmd5IHBvc3NpYmxlIGFmdGVyIGFycml2aW5nLiBCYXJpY2EgaW5pdGlhbGx5IGhhcyBubyBlbmVyZ3kgYW5kIG11c3QgZ2F0aGVyIGVuZXJneSBmb3IgaGVyIGZpcnN0IGp1bXAgZnJvbSB0aGUgZmxpZXMgYXJvdW5kIHBsYW50IDEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIHNlcXVlbmNlIG9mIHBsYW50cyBCYXJpY2Egc2hvdWxkIHRyYXZlbCB0byBhY2hpZXZlIGhlciBnb2FsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwKSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgWCwgWSBhbmQgRiAoMCAmbGU7IFgsIFkgJmxlOyAxMDAgMDAwLCAwICZsZTsgRiAmbGU7IDEwMDApIHNlcGFyYXRlZCBieSBzcGFjZXMsIG1lYW5pbmcgdGhhdCB0aGVyZSBpcyBhIHBsYW50IGF0IGNvb3JkaW5hdGVzIChYLCBZKSB3aXRoIEYgZmxpZXMgYXJvdW5kIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgcGxhbnQgaW4gdGhlIGlucHV0IGlzIHBsYW50IDEsIHRoZSBzZWNvbmQgaXMgcGxhbnQgMiBldGMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byBwbGFudHMgd2lsbCBzaGFyZSB0aGUgc2FtZSBwYWlyIG9mIGNvb3JkaW5hdGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgaW5wdXQgZGF0YSB3aWxsIGd1YXJhbnRlZSB0aGF0IGEgc2VxdWVuY2Ugb2YganVtcHMsIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgZmluYWwgZW5lcmd5IGxldmVsIG9uIHRoZSBmaXJzdCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdXRwdXQgYW4gaW50ZWdlciBMLCB0aGUgbnVtYmVyIG9mIHBsYW50cyBCYXJpY2Egc2hvdWxkIHRyYXZlbCwgaW5jbHVkaW5nIHBsYW50cyAxIGFuZCBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgZm9sbG93aW5nIEwgbGluZXMsIG91dHB1dCB0aGUgc2VxdWVuY2Ugb2YgcGxhbnRzIEJhcmljYSBzaG91bGQgdHJhdmVsLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 데이터를 추가한 사람: Acka
  • 빠진 조건을 찾은 사람: corea
  • 문제를 번역한 사람: myungwoo
  • 문제의 오타를 찾은 사람: planetarynebula