URI Online Judge | 2115

Production in Ekaterinburg

By XVII Maratona de Programação IME-USP, 2013 BR Brazil

Timelimit: 1

Ekaterinburg is a Russian city located at the border between Europe and Asia, Urals. It is the fourth largest city in Russia with more than 1.4 million inhabitants. The main economic activity of the city is related to the production of industrial machinery. The factories of the city produce a great part of all machines in Russia and export to many countries around the world. In particular the production of industrial tools is famous in the country. Tools are produced by highly specialized machines, and for each tool to be produced machines spend a predetermined time for its production.

One of the factories has only one of these machines and their manager needs your help to improve their productivity. Requests for tools arrive at the factory continuously, ie, earlier in the day not all requests can be processed because these will be available through the day. The manager thinks that employees are not choosing the right order in which requests are attended and he wants to analyze the sequences of requests from previous days. Thus, he asks you to determine, for a given day, the lowest possible moment that all applications would be completed.


The entry consists of several instances and ends with end of file (EOF).

Each instance starts with the number N (1 ≤ N ≤ 105) of tasks that will be processed during the day. The following N lines have the time di when the task will be available and the processing time pi of the task on the machine (1 ≤ di, pi ≤ 104). The processing start occurs at time 1.


For each instance of your program should print the lowest moment when the last task will finish its processing.

Sample Input Sample Output

10 2
6 1
4 3
1 2
1 4
1 1
1 3
5 2
5 3