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

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, P(1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.

출력

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

예제 입력 1

4
4 4
5 2
11 5
15 10
25 10

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE4MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjBcdWI4Y2MgXHVjYzQ0XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzFcdWFjYmRcdWM3NzRcdWIyOTQgXHVkMmI4XHViN2VkXHVjNzQ0IFx1YzgxNVx1YWUwMCBcdWMxOGRcdWM1ZDBcdWMxMWMgXHVjNmI0XHVjODA0XHVkNTU4XHViMmU0XHVhYzAwIFx1ZDJiOFx1YjdlZFx1Yzc1OCBcdWM1ZjBcdWI4Y2NcdWQwZjFcdWQwNmNcdWM1ZDAgXHVhYzExXHVjNzkwXHVhZTMwIFx1YWQ2Y1x1YmE0ZFx1Yzc3NCBcdWIwOThcdWMxMWMgMWttXHViOTdjIFx1YWMwMFx1YjI5NFx1YjM3MCAxTFx1Yzc1OCBcdWM1ZjBcdWI4Y2NcdWFjMDAgXHVjMGM4IFx1YjA5OFx1YWMwMFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0NCBcdWFjZTBcdWNlNThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViOWM4XHVjNzQ0XHVjNWQwIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWFkZjhcdWIwZTUgXHVhYzAwXHViMmU0XHVhYzAwXHViMjk0IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM1ZjBcdWI4Y2NcdWFjMDAgXHViMmU0IFx1YmU2MFx1YzljOCBcdWMyMThcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWIyZTRcdWQ1ODlcdWMyYTRcdWI3ZmRcdWFjOGNcdWIzYzQgXHVjODE1XHVhZTAwIFx1YWNmM1x1YWNmM1x1YzVkMCBcdWM1ZjBcdWI4Y2NcdWI5N2MgXHVjYzQ0XHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOGZjXHVjNzIwXHVjMThjXHVhYzAwIE5cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjODE1XHVhZTAwIFx1YzE4ZFx1YzVkMFx1YzExYyBcdWM5MTFcdWFjMDRcdWM1ZDAgXHVjYzI4XHViOTdjIFx1YmE0OFx1Y2Q5NFx1YjI5NCBcdWQ1ODlcdWM3MDRcdWIyOTQgXHViOWU0XHVjNmIwIFx1YzcwNFx1ZDVkOFx1ZDU1YyBcdWQ1ODlcdWM3MDRcdWM3NzRcdWJiYzBcdWI4NWMgXHVjOGZjXHVjNzIwXHVjMThjXHVjNWQwXHVjMTFjIFx1YmE0OFx1Y2Q5NFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWQ1ODlcdWM3NzRcdWIzYzQgXHVjMTMxXHVhY2JkXHVjNzc0XHVjNzU4IFx1ZDJiOFx1YjdlZFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjODhiXHVjNTQ0XHVjMTFjIFx1YzVmMFx1YjhjYyBcdWQwZjFcdWQwNmNcdWM1ZDBcdWIyOTQgXHVjNWYwXHViOGNjXHVjNzU4IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM1YzZcdWM3NzQgXHViOWNlXHVjNzc0IFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWI5Y2VcdWM3NzQgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOGZjXHVjNzIwXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCwgXHVhYzAxIFx1YzhmY1x1YzcyMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWI4Y2NcdWM3NTggXHVjNTkxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM1ZDBcdWMxMWMgXHViYTQ4XHVjZDk0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVhZTAwXHVjNzQwIFx1Yzc3Y1x1YzljMVx1YzEyMFx1Yzc3NFx1YWNlMCwgXHVjMTMxXHVhY2JkXHVjNzc0XHVjNzU4IFx1ZDJiOFx1YjdlZFx1YWNmYyBcdWM4ZmNcdWM3MjBcdWMxOGNcdWIzYzQgXHViYWE4XHViNDUwIFx1Yzc3Y1x1YzljMVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM3MjBcdWMxOGNcdWIyOTQgXHViYWE4XHViNDUwIFx1YzEzMVx1YWNiZFx1Yzc3NFx1Yzc1OCBcdWQyYjhcdWI3ZWRcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzcyMFx1YzE4Y1x1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDQgXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzcyMFx1YzE4Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggYSxiXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNCBcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwIGEoMSAmbGU7IGEgJmxlOyAxLDAwMCwwMDApXHViMjk0IFx1YzEzMVx1YWNiZFx1Yzc3NFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzcyMFx1YzE4YyBcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjLCBcdWFkZjhcdWI5YWNcdWFjZTAgYigxICZsZTsgYiAmbGU7IDEwMClcdWIyOTQgXHVhZGY4IFx1YzhmY1x1YzcyMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWNjNDRcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWI4Y2NcdWM3NTggXHVjNTkxXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE4rMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBMXHVhY2ZjIFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIEwoMSAmbGU7IEwgJmxlOyAxLDAwMCwwMDApXHVjNzQwIFx1YzEzMVx1YWNiZFx1Yzc3NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViOWM4XHVjNzQ0XHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhYywgUCgxICZsZTsgUCAmbGU7IDEsMDAwLDAwMClcdWIyOTQgXHVkMmI4XHViN2VkXHVjNWQwIFx1YzZkMFx1Yjc5OCBcdWM3ODhcdWIzNTggXHVjNWYwXHViOGNjXHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM2NDAgXHViOWM4XHVjNzQ0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODhjXHVkNDVjXHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViOWM4XHVjNzQ0XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWJjZjRcdWIyZTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzcyMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWJhNDhcdWNkOTRcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjljOFx1Yzc0NFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTYwXHVhY2JkXHVjNmIwIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXhwZWRpdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBncm91cCBvZiBjb3dzIGdyYWJiZWQgYSB0cnVjayBhbmQgdmVudHVyZWQgb24gYW4gZXhwZWRpdGlvbiBkZWVwIGludG8gdGhlIGp1bmdsZS4gQmVpbmcgcmF0aGVyIHBvb3IgZHJpdmVycywgdGhlIGNvd3MgdW5mb3J0dW5hdGVseSBtYW5hZ2VkIHRvIHJ1biBvdmVyIGEgcm9jayBhbmQgcHVuY3R1cmUgdGhlIHRydWNrJiMzOTtzIGZ1ZWwgdGFuay4gVGhlIHRydWNrIG5vdyBsZWFrcyBvbmUgdW5pdCBvZiBmdWVsIGV2ZXJ5IHVuaXQgb2YgZGlzdGFuY2UgaXQgdHJhdmVscy48XC9wPlxyXG5cclxuPHA+VG8gcmVwYWlyIHRoZSB0cnVjaywgdGhlIGNvd3MgbmVlZCB0byBkcml2ZSB0byB0aGUgbmVhcmVzdCB0b3duIChubyBtb3JlIHRoYW4gMSwwMDAsMDAwIHVuaXRzIGRpc3RhbnQpIGRvd24gYSBsb25nLCB3aW5kaW5nIHJvYWQuIE9uIHRoaXMgcm9hZCwgYmV0d2VlbiB0aGUgdG93biBhbmQgdGhlIGN1cnJlbnQgbG9jYXRpb24gb2YgdGhlIHRydWNrLCB0aGVyZSBhcmUgTiAoMSAmbHQ7PSBOICZsdDs9IDEwLDAwMCkgZnVlbCBzdG9wcyB3aGVyZSB0aGUgY293cyBjYW4gc3RvcCB0byBhY3F1aXJlIGFkZGl0aW9uYWwgZnVlbCAoMS4uMTAwIHVuaXRzIGF0IGVhY2ggc3RvcCkuPFwvcD5cclxuXHJcbjxwPlRoZSBqdW5nbGUgaXMgYSBkYW5nZXJvdXMgcGxhY2UgZm9yIGh1bWFucyBhbmQgaXMgZXNwZWNpYWxseSBkYW5nZXJvdXMgZm9yIGNvd3MuIFRoZXJlZm9yZSwgdGhlIGNvd3Mgd2FudCB0byBtYWtlIHRoZSBtaW5pbXVtIHBvc3NpYmxlIG51bWJlciBvZiBzdG9wcyBmb3IgZnVlbCBvbiB0aGUgd2F5IHRvIHRoZSB0b3duLiBGb3J0dW5hdGVseSwgdGhlIGNhcGFjaXR5IG9mIHRoZSBmdWVsIHRhbmsgb24gdGhlaXIgdHJ1Y2sgaXMgc28gbGFyZ2UgdGhhdCB0aGVyZSBpcyBlZmZlY3RpdmVseSBubyBsaW1pdCB0byB0aGUgYW1vdW50IG9mIGZ1ZWwgaXQgY2FuIGhvbGQuIFRoZSB0cnVjayBpcyBjdXJyZW50bHkgTCB1bml0cyBhd2F5IGZyb20gdGhlIHRvd24gYW5kIGhhcyBQIHVuaXRzIG9mIGZ1ZWwgKDEgJmx0Oz0gUCAmbHQ7PSAxLDAwMCwwMDApLjxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0b3BzIG5lZWRlZCB0byByZWFjaCB0aGUgdG93biwgb3IgaWYgdGhlIGNvd3MgY2Fubm90IHJlYWNoIHRoZSB0b3duIGF0IGFsbC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgZGVzY3JpYmluZyBhIGZ1ZWwgc3RvcDogVGhlIGZpcnN0IGludGVnZXIgaXMgdGhlIGRpc3RhbmNlIGZyb20gdGhlIHRvd24gdG8gdGhlIHN0b3A7IHRoZSBzZWNvbmQgaXMgdGhlIGFtb3VudCBvZiBmdWVsIGF2YWlsYWJsZSBhdCB0aGF0IHN0b3AuPFwvbGk+XHJcblx0PGxpPkxpbmUgTisyOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBMIGFuZCBQPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciBnaXZpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZ1ZWwgc3RvcHMgbmVjZXNzYXJ5IHRvIHJlYWNoIHRoZSB0b3duLiBJZiBpdCBpcyBub3QgcG9zc2libGUgdG8gcmVhY2ggdGhlIHRvd24sIG91dHB1dCAtMS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO US Open 2005 Contest > Gold 2번