시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 290 192 179 69.112%

문제

이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다. 이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.

이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다. 존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다. 여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.

N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.

모든 소가 농장에 입장하려면 얼마나 걸리는 지 구해보자.

입력

첫 줄에 100 이하의 양의 정수 N이 주어진다. 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다.

출력

모든 소가 농장에 입장하는 데 걸리는 최소 시간을 출력한다.

예제 입력 1

3
2 1
8 3
5 7

예제 출력 1

15

힌트

첫 번째 소는 2초에 도착하고 3초에 농장을 입장한다. 그 다음에는 세 번째 소가 5초에 도착하여 12초에 농장을 입장한다. 마지막으로 두 번째 소가 8초에 오는데, 세 번째 소가 검문을 받고 있으므로 12초까지 기다린 뒤 15초에 농장을 입장한다.

W3sicHJvYmxlbV9pZCI6IjE0NDY5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NFx1YzZjMyBcdWIxOGRcdWM3YTVcdWM3NTggXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWI5YzhcdWFkNmNcdWM3YTFcdWM3NzRcdWI4NWMgXHVhYzc0XHViMTA4XHViMjk0IFx1YWM4M1x1YzVkMCBcdWM5YzRcdWM4MDhcdWJhMzhcdWI5YWNcdWFjMDAgXHViMDljIFx1Yzg3NFx1Yzc0MCBcdWFkZjlcdWIyZThcdWM3NTggXHVhY2IwXHVjODE1XHVjNzQ0IFx1YjBiNFx1YjliMFx1YjJlNC4gXHViMThkXHVjN2E1IFx1YjQ1OFx1YjgwOFx1YzVkMCBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWM5ZDNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViYTc0IFx1YWRmY1x1Y2M5OCBcdWIxOGRcdWM3YTUgXHVjZDljXHVjMmUwXHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MmMgXHVjNzdjXHVjNzc0IFx1YWM3MFx1Yzc1OCBcdWM1YzZcdWIyZTQuIFx1Yzc3NCBcdWM3N2NcdWI4NWMgXHVjOGZjXHViY2MwIFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWJkODRcdWFjMWNcdWQ1NThcdWM2MDBcdWIyZTQuIFx1Y2U1Y1x1YWQ2Y1x1YjEyNCBcdWM5ZDFcdWM1ZDAgXHViMTgwXHViN2VjIFx1YWMwOCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YmZkMFx1YjljYyBcdWM1NDRcdWIyYzhcdWI3N2MsIFx1YjllNFx1YjE0NCBcdWNjMzhcdWFjMDBcdWQ1NThcdWIzNTggXHVhZDZkXHVjODFjIFx1YzgxNiBcdWM5ZGNcdWFlMzAgXHVjNjJjXHViOWJjXHVkNTNjXHVjNTQ0XHViNGRjXHVjNWQwXHViM2M0IFx1YzYyY1x1ZDU3NFx1YjI5NCBcdWNjMzhcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWM4YyBcdWI0MThcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM2YzMgXHViMThkXHVjN2E1XHVjNzU4IFx1YzE4YyBcdWM5MTEgXHVjODc0XHVjNzU4IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxOGNcdWFjMDAgXHVjODcwXHVhZTA4IFx1Yzc4OFx1YWUzNCBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWRmOFx1YjRlNFx1YjNjNCBcdWM1NDhcdWMyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzQgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YjI5NCBcdWJiMzhcdWM3NDAgXHVkNTU4XHViMDk4XHViYzE2XHVjNWQwIFx1YzVjNlx1YWNlMCwgXHVhZGY4IFx1YmIzOFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWI4MjRcdWJhNzQgXHVhYzEwXHVjMmRjXHVhZDAwXHVjNzU4IFx1YWUzOFx1YWNlMCBcdWFlMzQgXHVhYzgwXHViYjM4XHVjNzQ0IFx1YmMxYlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHVhYzAwIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YmE3NCBcdWM5MDRcdWM3NzQgXHVhZGY4IFx1YjljY1x1ZDA3YyBcdWFlMzhcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHVhYzAwIFx1Yzc3NCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHViN2VjIFx1YzY1NFx1YjJlNC4gXHVjMThjXHVhYzAwIFx1YjNjNFx1Y2MyOVx1ZDU1YyBcdWMyZGNcdWFjMDRcdWFjZmMgXHVhYzgwXHViYjM4XHViYzFiXHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzE4Y1x1YjljOFx1YjJlNCBcdWIyZTRcdWI5NzRcdWIyZTQuIChcdWJiM2NcdWI4NjAgXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuKSBcdWI0NTAgXHVjMThjXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWFjODBcdWJiMzhcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1YyBcdWMxOGNcdWFjMDAgNVx1Y2QwOFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWFjZTAgN1x1Y2QwOCBcdWIzZDlcdWM1NDggXHVhYzgwXHViYjM4XHVjNzQ0IFx1YmMxYlx1YzczY1x1YmE3NCwgOFx1Y2QwOFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NWMgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMxOGNcdWIyOTQgMTJcdWNkMDhcdWFlNGNcdWM5YzAgXHVjOTA0XHVjNzQ0IFx1YzExY1x1YzU3YyBcdWFjODBcdWJiMzhcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMxOGNcdWFjMDAgXHViMThkXHVjN2E1XHVjNWQwIFx1Yzc4NVx1YzdhNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM1YmNcdWI5YzhcdWIwOTggXHVhYzc4XHViOWFjXHViMjk0IFx1YzljMCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIDEwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMThjXHVjNzU4IFx1YjNjNFx1Y2MyOSBcdWMyZGNcdWFjMDFcdWFjZmMgXHVhYzgwXHViYjM4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMSAxLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPGJyPjxcL3A+Iiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1YzE4Y1x1YWMwMCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjNzg1XHVjN2E1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGJyPjxcL3A+IiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMThjXHViMjk0IDJcdWNkMDhcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhY2UwIDNcdWNkMDhcdWM1ZDAgXHViMThkXHVjN2E1XHVjNzQ0IFx1Yzc4NVx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzE4Y1x1YWMwMCA1XHVjZDA4XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YzVlYyAxMlx1Y2QwOFx1YzVkMCBcdWIxOGRcdWM3YTVcdWM3NDQgXHVjNzg1XHVjN2E1XHVkNTVjXHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMxOGNcdWFjMDAgOFx1Y2QwOFx1YzVkMCBcdWM2MjRcdWIyOTRcdWIzNzAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMThjXHVhYzAwIFx1YWM4MFx1YmIzOFx1Yzc0NCBcdWJjMWJcdWFjZTAgXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIDEyXHVjZDA4XHVhZTRjXHVjOWMwIFx1YWUzMFx1YjJlNFx1YjliMCBcdWI0YTQgMTVcdWNkMDhcdWM1ZDAgXHViMThkXHVjN2E1XHVjNzQ0IFx1Yzc4NVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIElJSSAoQnJvbnplKSIsImRlc2NyaXB0aW9uIjoiPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huLCBpbiBoaXMgb2xkIGFnZSwgaGFzIHVuZm9ydHVuYXRlbHkgYmVjb21lIGluY3JlYXNpbmdseSBncnVtcHkgYW5kIHBhcmFub2lkLiBGb3JnZXR0aW5nIHRoZSBleHRlbnQgdG8gd2hpY2ggYm92aW5lIGRpdmVyc2l0eSBoZWxwZWQgaGlzIGZhcm0gdHJ1bHkgZmxvdXJpc2ggb3ZlciB0aGUgeWVhcnMsIGhlIGhhcyByZWNlbnRseSBkZWNpZGVkIHRvIGJ1aWxkIGEgaHVnZSBmZW5jZSBhcm91bmQgdGhlIGZhcm0sIGRpc2NvdXJhZ2luZyBjb3dzIGZyb20gbmVpZ2hib3JpbmcgZmFybXMgZnJvbSB2aXNpdGluZywgYW5kIGNvbXBsZXRlbHkgcHJvaGliaXRpbmcgZW50cnkgZnJvbSBhIGhhbmRmdWwgb2YgbmVpZ2hib3JpbmcgZmFybXMuIFRoZSBjb3dzIGFyZSBxdWl0ZSB1cHNldCBieSB0aGlzIHN0YXRlIG9mIGFmZmFpcnMsIG5vdCBvbmx5IHNpbmNlIHRoZXkgY2FuIG5vIGxvbmdlciB2aXNpdCB3aXRoIHRoZWlyIGZyaWVuZHMsIGJ1dCBzaW5jZSBpdCBoYXMgY2F1c2VkIHRoZW0gdG8gY2FuY2VsIHBhcnRpY2lwYXRpb24gaW4gdGhlIEludGVybmF0aW9uYWwgTWlsa2luZyBPbHltcGlhZCwgYW4gZXZlbnQgdG8gd2hpY2ggdGhleSBsb29rIGZvcndhcmQgYWxsIHllYXIuPFwvcD5cclxuXHJcbjxwPk5laWdoYm9yaW5nIGNvd3MgdGhhdCBzdGlsbCBoYXZlIHRoZSBhYmlsaXR5IHRvIGVudGVyIEZhcm1lciBKb2huJiMzOTtzIHByb3BlcnR5IGZpbmQgdGhlIHByb2Nlc3MgaGFzIGJlY29tZSBtb3JlIGFyZHVvdXMsIGFzIHRoZXkgY2FuIGVudGVyIG9ubHkgdGhyb3VnaCBhIHNpbmdsZSBnYXRlIHdoZXJlIGVhY2ggY293IGlzIHN1YmplY3QgdG8gaW50ZW5zZSBxdWVzdGlvbmluZywgb2Z0ZW4gY2F1c2luZyB0aGUgY293cyB0byBxdWV1ZSB1cCBpbiBhIGxvbmcgbGluZS48XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggb2YgdGhlIE4mbmJzcDtjb3dzIHZpc2l0aW5nIHRoZSBmYXJtLCB5b3UgYXJlIHRvbGQgdGhlIHRpbWUgc2hlIGFycml2ZXMgYXQgdGhlIGdhdGUgYW5kIHRoZSBkdXJhdGlvbiBvZiB0aW1lIHJlcXVpcmVkIGZvciBoZXIgdG8gYW5zd2VyIGhlciBlbnRyeSBxdWVzdGlvbnMuIE9ubHkgb25lIGNvdyBjYW4gYmUgdW5kZXJnb2luZyBxdWVzdGlvbmluZyBhdCBhbnkgZ2l2ZW4gdGltZSwgc28gaWYgbWFueSBjb3dzIGFycml2ZSBuZWFyIHRoZSBzYW1lIHRpbWUsIHRoZXkgd2lsbCBsaWtlbHkgbmVlZCB0byB3YWl0IGluIGxpbmUgdG8gYmUgcHJvY2Vzc2VkIG9uZSBieSBvbmUuIEZvciBleGFtcGxlLCBpZiBhIGNvdyBhcnJpdmVzIGF0IHRpbWUgNSBhbmQgYW5zd2VycyBxdWVzdGlvbnMgZm9yIDcgdW5pdHMgb2YgdGltZSwgYW5vdGhlciBjb3cgYXJyaXZpbmcgYXQgdGltZSA4IHdvdWxkIG5lZWQgdG8gd2FpdCB1bnRpbCB0aW1lIDEyIHRvIHN0YXJ0IGFuc3dlcmluZyBxdWVzdGlvbnMgaGVyc2VsZi48XC9wPlxyXG5cclxuPHA+UGxlYXNlIGRldGVybWluZSB0aGUgZWFybGllc3QgcG9zc2libGUgdGltZSBieSB3aGljaCBhbGwgY293cyBhcmUgYWJsZSB0byBlbnRlciB0aGUgZmFybS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyZuYnNwO04sIGEgcG9zaXRpdmUgaW50ZWdlciBhdCBtb3N0IDEwMC4gRWFjaCBvZiB0aGUgbmV4dCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZXMgb25lIGNvdywgZ2l2aW5nIHRoZSB0aW1lIGl0IGFycml2ZXMgYW5kIHRoZSB0aW1lIGl0IHJlcXVpcmVzIGZvciBxdWVzdGlvbmluZzsgZWFjaCBvZiB0aGVzZSBudW1iZXJzIGFyZSBwb3NpdGl2ZSBpbnRlZ2VycyBhdCBtb3N0IDEsMDAwLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2UgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIHBvc3NpYmxlIHRpbWUgYXQgd2hpY2ggYWxsIHRoZSBjb3dzIGNvdWxkIGhhdmUgY29tcGxldGVkIHByb2Nlc3NpbmcuPFwvcD5cclxuIiwiaGludCI6IjxwPkhlcmUsIGZpcnN0IGNvdyBhcnJpdmVzIGF0IHRpbWUgMiBhbmQgaXMgcXVpY2tseSBwcm9jZXNzZWQuIFRoZSBnYXRlIHJlbWFpbnMgYnJpZWZseSBpZGxlIHVudGlsIHRoZSB0aGlyZCBjb3cgYXJyaXZlcyBhdCB0aW1lIDUsIGFuZCBiZWdpbnMgcHJvY2Vzc2luZy4gVGhlIHNlY29uZCBjb3cgdGhlbiBhcnJpdmVzIGF0IHRpbWUgOCBhbmQgd2FpdHMgdW50aWwgdGltZSA1Kzc9MTIgdG8gc3RhcnQgYW5zd2VyaW5nIHF1ZXN0aW9ucywgZmluaXNoaW5nIGF0IHRpbWUgMTIrMyA9IDE1LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d