Pilares
Laurêncio está competindo em um evento esportivo conhecido como pilares de gelo. Nesse evento, há () pilares de gelo em uma linha e são numerados de a da esquerda para a direita. O pilar tem uma durabilidade () e um peso () para . A cada segundo, Laurêncio pode reduzir a durabilidade de qualquer pilar em . Quando a durabilidade de um pilar se torna menor ou igual a , ele é derrubado e remove durabilidade igual a seu peso dos dois pilares adjacentes a ele (note que os pilares e 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 .
Em um cada uma das próximas linhas, há dois inteiros e .
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 |