uCoder | 1096 | Nível: 5 | Tempo Limite: 10
Produção em Ecaterimburgo
Adaptado por Erich Rodrigues
Competição: USP - Seletiva para Maratona de Programação, 2013
Ecaterimburgo é uma cidade russa localizada na fronteira entre a Europa e a Asia, nos montes Urais. E a quarta maior cidade da Rússia com mais de 1,4 milhões de habitantes. A principal atividade econômica da cidade está relacionada com a produção de máquinas industriais. As fábricas da cidade produzem boa parte de todas as máquinas usadas na Rússia e exportada para diversos países de todo o mundo. Em especial a produção de ferramentas industriais é famosa no país. As ferramentas são produzidas por máquinas altamente especializadas, e, para cada ferramenta a ser produzida as máquinas gastam um tempo pré-estabelecido para sua produção.
Uma das fábrica possui apenas uma dessas máquinas e seu gerente precisa da sua ajuda para melhorar sua produtividade. Os pedidos de ferramentas chegam na fábrica de forma contínua, isto é, no início do dia nem todos os pedidos podem ser processados, pois estes estarão disponíveis ao longo do dia. O gerente acha que os funcionários não estão escolhendo bem a ordem na qual os pedidos são atendidos e quer analisar as sequências de pedidos de dias anteriores. Dessa forma, ele pede que você determine, para um dado dia, o menor instante possível em que todos os pedidos estariam finalizados.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
Cada instância começa com o número N de tarefas que serão processadas no dia. As N linhas seguintes têm o tempo di em que a tarefa estará disponível e o tempo pi de processamento da tarefa na máquina. O início do processamento se dá no instante 1.
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância seu programa deverá imprimir o menor instante em que a tarefa que for processada por último terminará seu processamento.
A saída deve ser escrita na saída padrão.
Restrições
• 1 ≤ N ≤ 10^5
• 1 ≤ di , pi ≤ 10^4
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 |
13 |