| Fişierul intrare/ieşire: | hacker3.in, hacker3.out | Sursă | Junior Challenge 2012 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Junior Challenge •juniorc |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 312 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Hacker3
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 ai
- Varianta B in care hack-ul i poate fi rezolvat in timpul bi
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.
Date de intrare
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 ai si bi. Hack-urile trebuie rezolvate in ordine de la hack-ul 1 pana la hack-ul N.
Date de ieşire
Fişierul de ieşire hacker3.out va contine un singur numar reprezentand timpul minim petru a rezolva toate cele N hack-uri.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ ai ≤ 2.000.000.000
- 1 ≤ bi ≤ 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
Exemplu
| hacker3.in | hacker3.out |
|---|---|
| 2 1 4 3 1 | 3 |
