Informática Avançado - Semana 64

Pilares

Laurêncio está competindo em um evento esportivo conhecido como pilares de gelo. Nesse evento, há N (2 \leq N \leq 10^5) pilares de gelo em uma linha e são numerados de 1 a N da esquerda para a direita. O pilar i tem uma durabilidade D_i ( 1 \leq D_i \leq 10^9) e um peso W_i (0 \leq W_i \leq 10^9) para i = 1...N. A cada segundo, Laurêncio pode reduzir a durabilidade de qualquer pilar em 1. Quando a durabilidade de um pilar se torna menor ou igual a 0, ele é derrubado e remove durabilidade igual a seu peso dos dois pilares adjacentes a ele (note que os pilares 1 e N só tem um pilar adjacente). Ajude Laurêncio a calcular o menor tempo necessário para derrubar todos os pilares.

Entrada

A primeira linha contém o inteiro N.
Em um cada uma das próximas N linhas, há dois inteiros D_i e W_i.

Saída

Imprima o menor tempo necessário para que todos os pilares sejam derrubados.

Exemplo

ENTRADASAÍDA
5
5 5
7 2
8 1
2 0
1 3
14