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
| ENTRADA | SAÍDA |
| 5 5 5 7 2 8 1 2 0 1 3 | 14 |