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

ENTRADA	SAÍDA
5 5 5 7 2 8 1 2 0 1 3	14