시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 154 67 45 41.667%

문제

택희는 인터넷에서 노래를 다운받으려고 한다. 노래는 여러 조각으로 나누어져 있고, 정해진 순서대로 다운받아야 한다. 택희는 각 조각의 노래 길이와 다운로드 길이를 알고 있다.

택희는 노래를 모두 다운받기 전에 들으려고 한다. 음악이 중간에 끊여지면 분위기를 망치기 때문에, 한 번 듣기 시작하면 노래는 멈추지 않고 끝까지 재생해야 한다. 각 조각을 들으려면 그 조각을 모두 다운로드 해야 들을 수 있다.

택희가 음악을 끊김없이 들으려면, 다운로드 시작한지 몇 초 후에 들으면, 끊김 없이 노래를 들을 수 있는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 조각의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에는 노래의 길이 D와 다운로드하는데 걸리는 시간 V가 주어진다. (1 ≤ D,V ≤ 1000)

출력

첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다.

예제 입력 1

4
2 1
1 5
3 3
2 4

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjMyMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZTRcdWM2YjRcdWI4NWNcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWQwZGRcdWQ3NmNcdWIyOTQgXHVjNzc4XHVkMTMwXHViMTM3XHVjNWQwXHVjMTFjIFx1YjE3OFx1Yjc5OFx1Yjk3YyBcdWIyZTRcdWM2YjRcdWJjMWJcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIxNzhcdWI3OThcdWIyOTQgXHVjNWVjXHViN2VjIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM4MTVcdWQ1NzRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjJlNFx1YzZiNFx1YmMxYlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDBkZFx1ZDc2Y1x1YjI5NCBcdWFjMDEgXHVjODcwXHVhYzAxXHVjNzU4IFx1YjE3OFx1Yjc5OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViMmU0XHVjNmI0XHViODVjXHViNGRjIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQwZGRcdWQ3NmNcdWIyOTQgXHViMTc4XHViNzk4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWM2YjRcdWJjMWJcdWFlMzAgXHVjODA0XHVjNWQwIFx1YjRlNFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc0Y1x1YzU0NVx1Yzc3NCBcdWM5MTFcdWFjMDRcdWM1ZDAgXHViMDRhXHVjNWVjXHVjOWMwXHViYTc0IFx1YmQ4NFx1YzcwNFx1YWUzMFx1Yjk3YyBcdWI5ZGRcdWNlNThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NWMgXHViYzg4IFx1YjRlM1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzQgXHViMTc4XHViNzk4XHViMjk0IFx1YmE0OFx1Y2Q5NFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMDVkXHVhZTRjXHVjOWMwIFx1YzdhY1x1YzBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWM4NzBcdWFjMDFcdWM3NDQgXHViNGU0XHVjNzNjXHViODI0XHViYTc0IFx1YWRmOCBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYWE4XHViNDUwIFx1YjJlNFx1YzZiNFx1Yjg1Y1x1YjRkYyBcdWQ1NzRcdWM1N2MgXHViNGU0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDBkZFx1ZDc2Y1x1YWMwMCBcdWM3NGNcdWM1NDVcdWM3NDQgXHViMDRhXHVhZTQwXHVjNWM2XHVjNzc0IFx1YjRlNFx1YzczY1x1YjgyNFx1YmE3NCwgXHViMmU0XHVjNmI0XHViODVjXHViNGRjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YzljMCBcdWJhODcgXHVjZDA4IFx1ZDZjNFx1YzVkMCBcdWI0ZTRcdWM3M2NcdWJhNzQsIFx1YjA0YVx1YWU0MCBcdWM1YzZcdWM3NzQgXHViMTc4XHViNzk4XHViOTdjIFx1YjRlNFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTc4XHViNzk4XHVjNzU4IFx1YWUzOFx1Yzc3NCBEXHVjNjQwIFx1YjJlNFx1YzZiNFx1Yjg1Y1x1YjRkY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0IFZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEQsViAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHViMmU0XHVjNmI0XHViODVjXHViNGRjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWJhODcgXHVjZDA4IFx1ZDZjNFx1YzVkMCBcdWIxNzhcdWI3OThcdWI5N2MgXHViNGUzXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3NCwgXHViMDRhXHVhZTQwIFx1YzVjNlx1Yzc3NCBcdWI0ZTRcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViNzdjXHViYTc0LCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzIxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InppZGFyc2thIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyB3YW50cyB0byBkb3dubG9hZCBoaXMgZmF2b3JpdGUgc29uZyBmcm9tIHRoZSBpbnRlcm5ldC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNvbmcgaXMgZGl2aWRlZCBpbnRvIHNlZ21lbnRzIHRoYXQgbXVzdCBiZSBkb3dubG9hZGVkIGluIGZpeGVkIG9yZGVyLiBXZSBrbm93IHRoZSBsZW5ndGggYW5kIGRvd25sb2FkIHRpbWUgb2YgZWFjaCBzZWdtZW50IChib3RoIGFyZSBleHByZXNzZWQgaW4gc2Vjb25kcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIGl0JiMzOTtzIHBvc3NpYmxlLCBoZSB3YW50cyB0byBzdGFydCBsaXN0ZW5pbmcgdG8gaGlzIHNvbmcgYXMgc29vbiBhcyBwb3NzaWJsZSwgZXZlbiBiZWZvcmUgaXQmIzM5O3MgZG93bmxvYWRlZCwgd2l0aCBubyBpbnRlcnJ1cHRpb25zIChubyB3YWl0aW5nIGZvciBzb21lIHNlZ21lbnQgdG8gYmUgZG93bmxvYWRlZCBpbiB0aGUgbWlkZGxlIG9mIHRoZSBzb25nKS4gSGUgY2FuIHN0YXJ0IGxpc3RlbmluZyB0byBhIHNlZ21lbnQgb25seSBhZnRlciBpdCBoYXMgYmVlbiBjb21wbGV0ZWx5IGRvd25sb2FkZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBtaW5pbWFsIG51bWJlciBvZiBzZWNvbmRzIChmcm9tIHRoZSBtb21lbnQgdGhhdCBkb3dubG9hZCBzdGFydHMpIGFmdGVyIHdoaWNoIE1pcmtvIGNhbiBzdGFydCBsaXN0ZW5pbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSB0aGVyZSBpcyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgbnVtYmVyIG9mIHNlZ21lbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcywgdGhlcmUgYXJlIHR3byBpbnRlZ2VycywgRCBhbmQgViwgMSAmbGU7IEQsViAmbGU7IDEwMDAuIFRoZXNlIG51bWJlcnMgcmVwcmVzZW50IHNlZ21lbnRzIGluIHRoZSBvcmRlciB0aGV5IGhhdmUgdG8gYmUgZG93bmxvYWRlZC4gRCBpcyBsZW5ndGgsIFYgaXMgZG93bmxvYWQgdGltZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSB3cml0ZSB0aGUgbnVtYmVyIG9mIHNlY29uZHMgZnJvbSB0aGUgdGV4dC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=