시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB227066845730.712%

문제

어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.

현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.

입력

첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.

출력

첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI0MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWJjYmQgXHViNGYxXHViYzE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjNTU0XHViY2JkXHVjNWQwIG4oMSAmbGU7IG4gJmxlOyA1MCwwMDApXHVhYzFjXHVjNzU4IFx1ZDY0OFx1Yzc3NCBcdWQzMGNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNjQ4XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoeCwgeSlcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NFx1YjM3MCwgfGEgLSB4fCAmbGU7IDJcdWM3NzRcdWFjZTAgfGIgLSB5fCAmbGU7IDJcdWM3NzRcdWJhNzQgKHgsIHkpXHVjNWQwXHVjMTFjIChhLCBiKVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQ2NDhcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NFx1YzExYyB5ID0gVCgxICZsZTsgVCAmbGU7IDIwMCwwMDApXHVjNzdjIFx1YjU0Y1x1YWU0Y1x1YzljMCwgXHVjOTg5IFx1YzU1NFx1YmNiZFx1Yzc1OCBcdWM4MTVcdWMwYzFcdWFlNGNcdWM5YzAgXHVjNjI0XHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHViMjk0ICgwLCAwKVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVjNzc0XHViM2Q5IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViYTc0XHVjMTFjIFx1YzgxNVx1YzBjMVx1YzVkMCBcdWM2MjRcdWI5NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MTVcdWMwYzFcdWM1ZDAgXHVjNjI0XHViOTdjIFx1YjU0Y1x1Yzc1OCB4XHVjODhjXHVkNDVjXHViMjk0IFx1YzU0NFx1YmIzNCBcdWFjODNcdWM3NzRcdWIwOTggXHViNDE4XHVjNWI0XHViM2M0IFx1YzBjMVx1YWQwMFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG4sIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCB4LCB5XHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWJhYThcdWI0NTAgMFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YmE3MCwgeFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAxLDAwMCwwMDBcdWM3NzRcdWQ1NTgsIHlcdWM4OGNcdWQ0NWNcdWIyOTQgVFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNWQwIFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWM3NzggKDAsIDApXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjODE1XHVjMGMxXHVjNWQwIFx1YzYyNFx1Yjk3YyBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNDEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2F2ZSBDb3dzIDQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcm9ja3NsaWRlIGhhcyB0cmFwcGVkIEJlc3NpZSBpbiBoZXIgY2F2ZSwgYW5kIHNoZSBtdXN0IHNjYWxlIGEgdmVydGljYWwgcm9jayB3YWxsIGlmIHNoZSBpcyB0byBlc2NhcGUhICZuYnNwO0hhcHBpbHksIEJlc3NpZSBpcyBhbiBhY2NvbXBsaXNoZWQgcm9jayBjbGltYmVyLjxcL3A+XHJcblxyXG48cD5UaGluayBvZiB0aGUgcm9jayB3YWxsIGFzIGEgdHdvLWRpbWVuc2lvbmFsIHBsYW5lLCB3aXRoIGFuIHggKGhvcml6b250YWwpIGFuZCB6ICh2ZXJ0aWNhbCkgYXhpcy4gJm5ic3A7QmVzc2llIHN0YXJ0cyB3aXRoIGhlciBsZWZ0IGZyb250IGhvb2YgYXQgKDAsMCksIGFuZCBzaGUgbmVlZHMgdG8gY2xpbWIgdG8gdGhlIHRvcCBvZiB0aGUgd2FsbCwgYXQgeiA9IFQgKDEgJmx0Oz0gVCAmbHQ7PSAyMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHdhbGwgaGFzIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIHJvY2tzIHRoYXQgc3RpY2sgb3V0IGFuZCBwcm92aWRlIGhvb2Zob2xkcyBmb3IgQmVzc2llLiAmbmJzcDtJZiBCZXNzaWUgaXMgY3VycmVudGx5IGhvbGRpbmcgb24gdG8gb25lIG9mIHRoZXNlIGhvb2Zob2xkcyB3aXRoIGhlciBsZWZ0IGZyb250IGhvb2YsIHNoZSBjYW4gcmVhY2ggYSBuZXcgaG9vZmhvbGQgb25seSBpZiBpdCBpcyBhdCBtb3N0IDIgdW5pdHMgYXdheSBpbiBpdHMgeCBjb29yZGluYXRlIGFuZCBhbHNvIGF0IG1vc3QgMiB1bml0cyBhd2F5IGluIGl0cyB6IGNvb3JkaW5hdGUgZnJvbSBoZXIgY3VycmVudCBob2xkLiBOb3RlIHRoYXQgQmVzc2llIGNhbiBtb3ZlIHRvIGEgaG9vZmhvbGQgYWJvdmUsIGJlc2lkZSwgb3IgYmVsb3cgaGVyLCBhcyBsb25nIGFzIGl0cyB4IGFuZCB6IGNvb3JkaW5hdGVzIGFyZSBib3RoIHdpdGhpbiAyIHVuaXRzIG9mIGhlciBjdXJyZW50IGhvb2Zob2xkLiBXaGVuIHNoZSBtb3ZlcywgaGVyIGZyb250IGxlZnQgaG9vZiBlbmRzIHVwIG9uIHRoZSBuZXcgaG9vZmhvbGQuPFwvcD5cclxuXHJcbjxwPkhlbHAgQmVzc2llIGRldGVybWluZSBpZiBzaGUgY2FuIHNjYWxlIHRoZSB3YWxsICh0aGF0IGlzLCBpZiBzaGUgY2FuIHJlYWNoIGFueSBob29maG9sZCBhdCBoZWlnaHQgVCksIGFuZCBpZiBzbywgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGhvb2Zob2xkcyBzaGUgbXVzdCB1c2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgVDxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgcmVwcmVzZW50IHRoZSAoeCx6KSBjb29yZGluYXRlcyBvZiBhIGhvb2Zob2xkLiAmbmJzcDtFYWNoIHggY29vcmRpbmF0ZSB3aWxsIGJlIGluIHRoZSByYW5nZSAwIC4uIDEsMDAwLDAwMCwgYW5kIGVhY2ggeiBjb29yZGluYXRlIHdpbGwgYmUgaW4gdGhlIHJhbmdlIDAgLi4gVC4gJm5ic3A7VGhlIGluaXRpYWwgZm9vdGhvbGQgKDAsMCkgZG9lcyBub3QgYXBwZWFyIGluIHRoaXMgbGlzdC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgcmVxdWlyZWQgdG8gcmVhY2ggdGhlIHRvcCBvciAtMSBpZiBpdCBpcyAmbmJzcDtpbXBvc3NpYmxlIHRvIHJlYWNoIHRoZSB0b3AuICZuYnNwO1RoZSBpbml0aWFsIGhvb2Zob2xkIGF0ICgwLDApIGRvZXMgbm90ICZuYnNwO2NvdW50IGFzIGEgc3RlcC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO US Open 2004 Contest > Orange 4번

  • 문제를 번역한 사람: author10
  • 문제의 오타를 찾은 사람: lyzqm
  • 빠진 조건을 찾은 사람: Nada