==Include(page="template/taskheader" task_id="calatorie")==
 
==Include(page="template/raw")==
 
Calatorie interplanetara
 
 
 
O nava spatiala trebuie sa calatoreasca de la planeta 1 la planeta 2, apoi de la planeta 2 la planeta 3 si tot asa pana cand ajunge la planeta N. Cand calatoreste de la planeta K la planeta K+1 nava spatiala are doua optiuni: viteza normala sau superviteza. Folosind viteza normala, timpul calatoriei de la planeta K la planeta K+1 este N[k] unitati de timp. Folosind superviteza, timpul calatoriei dintre planetele K si K+1 este H[k] unitati de timp. Pilotul navei spatiale este interesat sa consume cat mai putin combustibil in calatoria sa. El stie ca formula pentru consumul de combustibil este: N[TOTAL] + H[TOTAL]^4, unde N[TOTAL] este totalul unitatilor de timp in care a folosit viteza normala, iar H[TOTAL] este totalul unitatilor de timp in care a folosit superviteza. De exemplu, sa presupunem ca sunt 5 planete. De la planeta 1 la planeta 2 nava spatiala calatoreste 60 unitati de timp folosind viteza normala. De la planeta 2 la planeta 3 nava spatiala calatoreste 3 unitati de timp folosind superviteza.
De la planeta 3 la planeta 4 nava spatiala calatoreste 40 de unitati de timp folosind viteza normala. De la planeta 4 la planeta 5 nava spatiala calatoreste 7 unitati de timp folosind superviteza. N[TOTAL] = 60 + 40 = 100 si H[TOTAL] = 3 + 7 = 10. Consumul de combustibil este 100 + 10^4 = 10100.
 
h2. Cerinta
 
Determinati Consumul minim de combustibil necesar calatoriei de la planeta 1 la planeta N.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare calatorie.in contine numarul de teste T. Urmatoarele linii descriu cele T teste. Prima linie a fiecarui test contine numarul de planete N. Urmatoarele N-1 linii contin 2 numere intregi, N[K] si H[K], pentru K = 1,2,..,N-1.
 
h2. Date de Iesire
 
Pentru fiecare test afisati in fisierul calatorie.out o singura linie care sa respecte urmatorul format: "Consumul minim = XXX.", unde XXX trebuie inlocuit cu numarul gasit de programul vostru.
 
h2. Restrictii
 
o 1 <= N <= 50
 
o 1 <= T <= 155
 
o 1 <= N[k] <= 10^8
 
o 1 <= H[k] <= 10
 
h2. Exemplu
 
 
|calatorie.in |calatorie.out |
 
|2 |Consumul minim = 2296. |
| | |
|4 |Consumul minim = 52507. |
| | |
|1000 3 | |
| | |
|5000 2 | |
| | |
|8000 4 | |
| | |
|6 | |
| | |
|10000 1 | |
| | |
|3547 2 | |
| | |
|36782 7 | |
| | |
|2178 4 | |
| | |
|67428 9 | |

==Include(page="template/taskheader" task_id="calatorie")==
 
O nava spatiala trebuie sa calatoreasca de la planeta $1$ la planeta $2$, apoi de la planeta $2$ la planeta $3$ si tot asa pana cand ajunge la planeta $N$. Cand calatoreste de la planeta $K$ la planeta $K+1$ nava spatiala are doua optiuni: viteza normala sau superviteza. Folosind viteza normala, timpul calatoriei de la planeta $K$ la planeta $K+1$ este $N{~k~}$ unitati de timp. Folosind superviteza, timpul calatoriei dintre planetele $K$ si $K+1$ este $H{~k~}$ unitati de timp. Pilotul navei spatiale este interesat sa consume cat mai putin combustibil in calatoria sa. El stie ca formula pentru consumul de combustibil este: {$N{~TOTAL~} + H{~TOTAL~}^4^$}, unde {$N{~TOTAL~}$} este totalul unitatilor de timp in care a folosit viteza normala, iar H{~TOTAL~} este totalul unitatilor de timp in care a folosit superviteza. De exemplu, sa presupunem ca sunt $5$ planete. De la planeta $1$ la planeta $2$ nava spatiala calatoreste $60$ unitati de timp folosind viteza normala. De la planeta $2$ la planeta $3$ nava spatiala calatoreste $3$ unitati de timp folosind superviteza.
De la planeta $3$ la planeta $4$ nava spatiala calatoreste $40$ de unitati de timp folosind viteza normala. De la planeta $4$ la planeta $5$ nava spatiala calatoreste $7$ unitati de timp folosind superviteza. {$N{~TOTAL~} = 60 + 40 = 100$} si {$H{~TOTAL~} = 3 + 7 = 10$}. Consumul de combustibil este {$100 + 10^4^ = 10100$}.
 
h2. Cerinta
 
Determinati Consumul minim de combustibil necesar calatoriei de la planeta $1$ la planeta $N$.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare $calatorie.in$ contine numarul de teste $T$. Urmatoarele linii descriu cele $T$ teste. Prima linie a fiecarui test contine numarul de planete $N$. Urmatoarele $N-1$ linii contin $2$ numere intregi, $N{~K~}$ si $H{~K~}$, pentru $K = 1,2,..,N-1$.
 
h2. Date de Iesire
 
Pentru fiecare test afisati in fisierul $calatorie.out$ o singura linie care sa respecte urmatorul format: $Consumul minim = XXX.$, unde $XXX$ trebuie inlocuit cu numarul gasit de programul vostru.
 
h2. Restrictii
 
* $1 ≤ N ≤ 50$
* $1 ≤ T ≤ 155$
* $1 ≤ N{~k~} ≤ 10^8^$
* $1 ≤ H{~k~} ≤ 10$
 
h2. Exemplu
 
table(example). |_. calatorie.in |_. calatorie.out |
| 2
4
1000 3
5000 2
8000 4
6
10000 1
3547 2
36782 7
2178 4
67428 9
| Consumul minim = 2296.
Consumul minim = 52507. |
 
==Include(page="template/taskfooter" task_id="calatorie")==

==Include(page="template/taskfooter" task_id="calatorie")==

574