Meşterul Vasile are o firmă de microprocesoare. Pe 1 ianuarie el îşi planifică activitatea pentru următoarele n zile. Analizând graficul de producţie pentru cele n zile, Vasile ştie că în ziua i firma sa poate produce cel mult pi microprocesoare, costul de producţie al unui microprocesor fiind cpi (1 ≤ i ≤ n). Analizând situaţia comenzilor, Vasile ştie că în ziua i el trebuie să livreze exact nri microprocesoare (1 ≤ i ≤ n). Microprocesoarele care nu sunt livrate pot fi trimise la depozit pentru a fi utilizate ulterior. În noaptea dintre zilele i şi i + 1 pot fi depozitate cel mult di microprocesoare, costul depozitării unui microprocesor fiind cdi (1 ≤ i < n).
Cerinţă
Scrieţi un program care să determine care este suma minimă pe care meşterul Vasile trebuie să o cheltuiască pentru producţie şi depozitare astfel încât să satisfacă toate comenzile pentru cele n zile.
Date de intrare
Fişierul de intrare micro.in conţine pe prima linie numărul natural n. Pe următoarele n linii se află informaţii despre producţie şi comenzi. Mai exact, pe cea de a i-a linie dintre cele n se află trei numere naturale separate prin spaţii: picpinri (1 ≤ i ≤ n). Pe următoarele n - 1 linii se află informaţii despre depozitare. Mai exact, pe linia i dintre cele n - 1 (1 ≤ i ≤ n - 1) se află două numere naturale separate prin spaţiu dicdi.
Date de ieşire
Fişierul de ieşire micro.out va conţine o singură linie pe care va fi scris un singur număr întreg: suma minimă necesară pentru satisfacerea tuturor comenzilor sau valoarea -1 dacă acest lucru nu este posibil.
Restricţii
1 ≤ n ≤ 100.000 0 ≤ pi, cpi, nri ≤ 1.000.000.000, pentru 1 ≤ i ≤ n 0 ≤ di, cdi ≤ 1.000.000.000, pentru 1 ≤ i ≤ n - 1
Numărul din fişierul de ieşire se încadrează în tipul întreg pe 64 biţi cu semn
Exemple
micro.in
micro.out
Explicaţii
3
10 4 1
2 2 6
11 10 8
7 3
3 5
116
În prima zi pot fi produse maxim 10 microprocesoare, la 4 lei microprocesorul şi trebuie să fie livrat un singur microprocesor. Cost pentru ziua 1: 4 lei. Peste noapte pot fi stocate doar 7 microprocesoare, la costul de 3 lei bucata.
A doua zi sunt produse două microprocesoare cu 2 lei bucata şi trebuie să fie livrate şase. Vom livra cele două microprocesoare produse + 4 din depozit (stocate din prima zi). Cost pentru ziua 2: 2 * 2 + (4 + 3) * 4 = 32.
A treia zi pot fi produse maxim 11 microprocesoare la costul de 10 lei bucata şi trebuie să fie livrate 8 microprocesoare. Este preferabil să livrăm 8 procesoare produse în ziua 3 cu 10 lei bucata adică în total 80 lei. Cost total: 4 + 32 + 80 = 116.