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

문제

N (1 ≤ N ≤ 50,000) 명의 곡예사들로 인간 탑을 쌓으려고 한다. 한 사람이 한 층을 이루게 되어, 탑은 총 N층이 된다. 어떤 층에 있는 사람은 그보다 높은 층에 있는 모든 사람들의 몸무게의 합만큼을 견뎌야 한다.

각각의 곡예사들은 두 가지 정보로 나타내어지는데, 하나는 몸무게 (1 ≤ Wi ≤ 10,000) 이고, 다른 하나는 버티는 힘 (1 ≤ Si ≤ 1,000,000,000) 이다. 그리고 어떤 탑이 있을 때, 각각의 곡예사들에 대해 위험도를 계산할 수 있는데, 이는 (그보다 높은 층에 있는 모든 사람들의 몸무게의 합) - (그의 버티는 힘) 과 같다. 각각의 곡예사들의 위험도들 중에서 가장 큰 값을 최대 위험도라고 한다.

탑 쌓기에 참여하는 곡예사들이 정해졌을 때, 이들을 쌓는 방법은 여러 가지가 있을 수 있다. 그 중 최대 위험도의 가능한 최솟값을 구하시오.

입력

첫째 줄에 N이 들어온다.

둘째 줄부터 N+1번째 줄까지 N개의 줄이 차례대로 들어온다. 각 줄에서는 두 정수 Wi, Si가 공백으로 구분되어 들어온다.

출력

첫째 줄에 가능한 최대 위험도의 최솟값을 출력한다.

예제 입력 1

3
10 3
2 5
3 3

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIxMjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzhcdWFjMDQgXHVkMGQxIFx1YzMxM1x1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+TiAoMSAmbGU7Jm5ic3A7TiAmbGU7IDUwLDAwMCkgXHViYTg1XHVjNzU4IFx1YWNlMVx1YzYwOFx1YzBhY1x1YjRlNFx1Yjg1YyBcdWM3NzhcdWFjMDQgXHVkMGQxXHVjNzQ0IFx1YzMxM1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTVjIFx1Y2UzNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFjOGMgXHViNDE4XHVjNWI0LCBcdWQwZDFcdWM3NDAgXHVjZDFkIE5cdWNlMzVcdWM3NzQgXHViNDFjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjZTM1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhZGY4XHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0MCBcdWNlMzVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHViYWI4XHViYjM0XHVhYzhjXHVjNzU4IFx1ZDU2OVx1YjljY1x1ZDA3Y1x1Yzc0NCBcdWFjYWNcdWIzOGNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVhY2UxXHVjNjA4XHVjMGFjXHViNGU0XHVjNzQwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjODE1XHViY2Y0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVkNTU4XHViMDk4XHViMjk0IFx1YmFiOFx1YmIzNFx1YWM4YyAoMSAmbGU7Jm5ic3A7VzxzdWI+aTxcL3N1Yj4gJmxlOyAxMCwwMDApIFx1Yzc3NFx1YWNlMCwgXHViMmU0XHViOTc4IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJjODRcdWQyZjBcdWIyOTQgXHVkNzk4ICgxICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAsMDAwKSBcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1YjRcdWI1YTQgXHVkMGQxXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZTFcdWM2MDhcdWMwYWNcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzcwNFx1ZDVkOFx1YjNjNFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IChcdWFkZjhcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzQwIFx1Y2UzNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5KSAtIChcdWFkZjhcdWM3NTggXHViYzg0XHVkMmYwXHViMjk0IFx1ZDc5OCkgXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNlMVx1YzYwOFx1YzBhY1x1YjRlNFx1Yzc1OCBcdWM3MDRcdWQ1ZDhcdWIzYzRcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBcdWM3MDRcdWQ1ZDhcdWIzYzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDEgXHVjMzEzXHVhZTMwXHVjNWQwIFx1Y2MzOFx1YzVlY1x1ZDU1OFx1YjI5NCBcdWFjZTFcdWM2MDhcdWMwYWNcdWI0ZTRcdWM3NzQgXHVjODE1XHVkNTc0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViNGU0XHVjNzQ0IFx1YzMxM1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzkxMSBcdWNkNWNcdWIzMDAgXHVjNzA0XHVkNWQ4XHViM2M0XHVjNzU4IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWMxMWNcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBXPHN1Yj5pPFwvc3ViPiwgUzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1YzcwNFx1ZDVkOFx1YjNjNFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3cgQWNyb2JhdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIGNvd3MgKG51bWJlcmVkIDEuLk4pIGFyZSBwbGFubmluZyB0byBydW4gYXdheSBhbmQgam9pbiB0aGUgY2lyY3VzLiBUaGVpciBob29mZWQgZmVldCBwcmV2ZW50IHRoZW0gZnJvbSB0aWdodHJvcGUgd2Fsa2luZyBhbmQgc3dpbmdpbmcgZnJvbSB0aGUgdHJhcGV6ZSAoYW5kIHRoZWlyIGxhc3QgYXR0ZW1wdCBhdCBmaXJpbmcgYSBjb3cgb3V0IG9mIGEgY2Fubm9uIG1ldCB3aXRoIGEgZGlzbWFsIGZhaWx1cmUpLiBUaHVzLCB0aGV5IGhhdmUgZGVjaWRlZCB0byBwcmFjdGljZSBwZXJmb3JtaW5nIGFjcm9iYXRpYyBzdHVudHMuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIGFyZW4mIzM5O3QgdGVycmlibHkgY3JlYXRpdmUgYW5kIGhhdmUgb25seSBjb21lIHVwIHdpdGggb25lIGFjcm9iYXRpYyBzdHVudDogc3RhbmRpbmcgb24gdG9wIG9mIGVhY2ggb3RoZXIgdG8gZm9ybSBhIHZlcnRpY2FsIHN0YWNrIG9mIHNvbWUgaGVpZ2h0LiBUaGUgY293cyBhcmUgdHJ5aW5nIHRvIGZpZ3VyZSBvdXQgdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgc2hvdWxkIGFycmFuZ2UgdGhlbXNlbHZlcyBpdGhpbiB0aGlzIHN0YWNrLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBOIGNvd3MgaGFzIGFuIGFzc29jaWF0ZWQgd2VpZ2h0ICgxICZsdDs9IFdfaSAmbHQ7PSAxMCwwMDApIGFuZCBzdHJlbmd0aCAoMSAmbHQ7PSBTX2kgJmx0Oz0gMSwwMDAsMDAwLDAwMCkuIFRoZSByaXNrIG9mIGEgY293IGNvbGxhcHNpbmcgaXMgZXF1YWwgdG8gdGhlIGNvbWJpbmVkIHdlaWdodCBvZiBhbGwgY293cyBvbiB0b3Agb2YgaGVyIChub3QgaW5jbHVkaW5nIGhlciBvd24gd2VpZ2h0LCBvZiBjb3Vyc2UpIG1pbnVzIGhlciBzdHJlbmd0aCAoc28gdGhhdCBhIHN0cm9uZ2VyIGNvdyBoYXMgYSBsb3dlciByaXNrKS4gWW91ciB0YXNrIGlzIHRvIGRldGVybWluZSBhbiBvcmRlcmluZyBvZiB0aGUgY293cyB0aGF0IG1pbmltaXplcyB0aGUgZ3JlYXRlc3QgcmlzayBvZiBjb2xsYXBzZSBmb3IgYW55IG9mIHRoZSBjb3dzLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgaW50ZWdlciBOLjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGRlc2NyaWJlcyBjb3cgaSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIFdfaSBhbmQgU19pLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIsIGdpdmluZyB0aGUgbGFyZ2VzdCByaXNrIG9mIGFsbCB0aGUgY293cyBpbiBhbnkgb3B0aW1hbCBvcmRlcmluZyB0aGF0IG1pbmltaXplcyB0aGUgcmlzay48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=