hacker3

Hacker3

== include(page="template/taskheader" task_id="hacker3") ==

Poveste şi cerinţă...

KL3.14 a primit o sarcina foarte importanta. El trebuie sa rezolve $N$ hackuri in ordinea in care acestea apar. Un hack poate fi rezolvat in $2$ modalitati:
 
* Varianta $A$ in care hack-ul $i$ poate fi rezolvat in timpul $a{~i~}$
* Varianta $B$ in care hack-ul $i$ poate fi rezolvat in timpul $b{~i~}$
 
KL3.14 trebuie sa rezolve hack-urile in timp minim doar ca a intervenit o problema. El a aflat ca daca rezolva un hack in varianta $A$ atunci toate hack-urile de la $i+1$ la $N$ vor fi rezolvate de $2$ ori mai incet. Mai exact timpul sa rezolve un hack va fi dublat. Din moment ce KL3.14 tocmai a aflat ca trebuie sa se upgradeze la un alt nivel si ca nu mai are timp sa rezolve hack-urile el va roaga pe voi sa le rezolvati in timp minim.

h2. Date de intrare

Fişierul de intrare $hacker3.in$ ...

Fişierul de intrare $hacker3.in$ ca contine un numar $N$ reprezentand numarul de hack-uri ce trebuie rezolvate. Pe urmatoarele $N$ linii se vor afla cate $2$ numere naturale $a{~i~}$ si $b{~i~}$. Hack-urile trebuie rezolvate in ordine de la hack-ul $1$ pana la hack-ul $N$.

h2. Date de ieşire

În fişierul de ieşire $hacker3.out$ ...

Fişierul de ieşire $hacker3.out$ va contine un singur numar reprezentand timpul minim petru a rezolva toate cele $N$ hack-uri.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ a{~i~} ≤ 2.000.000.000$
* $1 ≤ b{~i~} ≤ 2.000.000.000$
* pentru $10%$ din teste $N ≤ 15$
* pentru alte $10%$ din teste $N ≤ 100$
* pentru alte $20%$ din teste $N ≤ 1000$
* pentru alte $30%$ din teste $N ≤ 10.000$

h2. Exemplu
table(example). |_. hacker3.in |_. hacker3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
1 4
3 1
| 3

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="hacker3") ==