시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 31 26 54.167%

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다. 

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입력

첫 줄에는 일의 갯수인 N을 받고

두번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

출력

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

예제 입력 1

4
3 5
8 14
5 20
1 16

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjYwNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjMDQgXHVhZDAwXHViOWFjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzFcdWMyZTRcdWQ1NWMgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YWQwMFx1YjlhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzc4IFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC4gXHVhZGY4XHViMjk0IE5cdWFjMWNcdWM3NTggXHVkNTc0XHVjNTdjXHVkNTYwIFx1Yzc3Y1x1YzVkMCZuYnNwOygxJmx0Oz1OJmx0Oz0xMDAwKSBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWU0XHVhY2JjXHViMmU0LiZuYnNwOyhcdWM2YjBcdWM3MjBcdWI5N2MgXHVjOWRjXHVhY2UwLCBcdWI5YzhcdWFkN2ZcdWFjMDRcdWM3NDQgXHVjZTU4XHVjNmIwXHVhY2UwLCBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhY2UwXHVjZTU4XHViMjk0IFx1YjRmMVx1Yzc1OCk8XC9wPlxyXG5cclxuPHA+XHVjODc0XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZDAwXHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhZGY4XHViMjk0IFx1YjA1ZFx1YjBiNFx1YzU3Y1x1YjljYyBcdWQ1NThcdWIyOTQgXHVjNzdjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YzY0NFx1YzEzMVx1YjQyMCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc0NCBUX2koMSZsdDs9VF9pJmx0Oz0xLDAwMCkgXHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3MCwgXHViMDVkXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBTX2koMSZsdDs9U19pJmx0Oz0xLDAwMCwwMDApIFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNzU4IFx1YzJkY1x1Yzc5MVx1Yzc0NCB0ID0gMFx1YzczY1x1Yjg1YyBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3N2MgXHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWFkZjgmbmJzcDtcdWM3N2NcdWM3NDQgXHViOWM4XHVjZTYwJm5ic3A7XHViNTRjIFx1YWU0Y1x1YzljMCBcdWFkZjggXHVjNzdjXHViOWNjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjODc0XHVjNzQwIFx1YjJhNlx1YzdhMCBcdWM3OTBcdWIyOTQgXHVhYzc4IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjJm5ic3A7XHVjODFjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWM4YyZuYnNwO1x1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU1Y1x1YjNjNFx1YzVkMFx1YzExYyZuYnNwO1x1Yzg3NFx1Yzc3NCZuYnNwO1x1YWMwMFx1YzdhNSBcdWIyYTZcdWFjOGMgXHVjNzdjXHVjNWI0XHViMDk4XHViM2M0IFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3NTggXHVhYzJmXHVjMjE4XHVjNzc4IE5cdWM3NDQgXHViYzFiXHVhY2UwPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHVjOTA0XHVhZTRjXHVjOWMwIFRfaVx1YzY0MCBTX2lcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHViMjk0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3NFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjUgXHVkNTU4XHViNzdjLiBcdWM4NzRcdWM3NzQgXHVjODFjXHVjMmRjXHVhYzA0XHVjNWQwIFx1Yzc3Y1x1Yzc0NCBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAtMSBcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYwNjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaW1lIE1hbmFnZW1lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPkV2ZXIgdGhlIG1hdHVyaW5nIGJ1c2luZXNzbWFuLCBGYXJtZXIgSm9obiByZWFsaXplcyB0aGF0IGhlIG11c3QgbWFuYWdlIGhpcyB0aW1lIGVmZmVjdGl2ZWx5LiBIZSBoYXMgTiBqb2JzIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OICgxICZsdDs9IE4gJmx0Oz0gMSwwMDApIHRvIGFjY29tcGxpc2ggKGxpa2UgbWlsa2luZyB0aGUgY293cywgY2xlYW5pbmcgdGhlIGJhcm4sIG1lbmRpbmcgdGhlIGZlbmNlcywgYW5kIHNvIG9uKS48XC9wPlxyXG5cclxuPHA+VG8gbWFuYWdlIGhpcyB0aW1lIGVmZmVjdGl2ZWx5LCBoZSBoYXMgY3JlYXRlZCBhIGxpc3Qgb2YgdGhlIGpvYnMgdGhhdCBtdXN0IGJlIGZpbmlzaGVkLiBKb2IgaSByZXF1aXJlcyBhIGNlcnRhaW4gYW1vdW50IG9mIHRpbWUgVF9pICgxICZsdDs9IFRfaSAmbHQ7PSAxLDAwMCkgdG8gY29tcGxldGUgYW5kIGZ1cnRoZXJtb3JlIG11c3QgYmUgZmluaXNoZWQgYnkgdGltZSBTX2kgKDEgJmx0Oz0gU19pICZsdDs9IDEsMDAwLDAwMCkuIEZhcm1lciBKb2huIHN0YXJ0cyBoaXMgZGF5IGF0IHRpbWUgdD0wIGFuZCBjYW4gb25seSB3b3JrIG9uIG9uZSBqb2IgYXQgYSB0aW1lIHVudGlsIGl0IGlzIGZpbmlzaGVkLjxcL3A+XHJcblxyXG48cD5FdmVuIGEgbWF0dXJpbmcgYnVzaW5lc3NtYW4gbGlrZXMgdG8gc2xlZXAgbGF0ZTsgaGVscCBGYXJtZXIgSm9obiBkZXRlcm1pbmUgdGhlIGxhdGVzdCBoZSBjYW4gc3RhcnQgd29ya2luZyBhbmQgc3RpbGwgZmluaXNoIGFsbCB0aGUgam9icyBvbiB0aW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBUX2kgYW5kIFNfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbGF0ZXN0IHRpbWUgRmFybWVyIEpvaG4gY2FuIHN0YXJ0IHdvcmtpbmcgb3IgLTEgaWYgRmFybWVyIEpvaG4gY2Fubm90IGZpbmlzaCBhbGwgdGhlIGpvYnMgb24gdGltZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+RmFybWVyIEpvaG4gaGFzIDQgam9icyB0byBkbywgd2hpY2ggdGFrZSAzLCA4LCA1LCBhbmQgMSB1bml0cyBvZiB0aW1lLCByZXNwZWN0aXZlbHksIGFuZCBtdXN0IGJlIGNvbXBsZXRlZCBieSB0aW1lIDUsIDE0LCAyMCwgYW5kIDE2LCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIG11c3Qgc3RhcnQgdGhlIGZpcnN0IGpvYiBhdCB0aW1lIDIuIFRoZW4gaGUgY2FuIGRvIHRoZSBzZWNvbmQsIGZvdXJ0aCwgYW5kIHRoaXJkIGpvYnMgaW4gdGhhdCBvcmRlciB0byBmaW5pc2ggb24gdGltZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO November 2008 Contest > Silver 3번

  • 문제를 번역한 사람: inspire12
  • 문제의 오타를 찾은 사람: isku