Fişierul intrare/ieşire:hacker3.in, hacker3.outSursăJunior Challenge 2012
AutorEugenie Daniel PosdarascuAdăugată dejuniorcJunior Challenge juniorc
Timp execuţie pe test0.4 secLimită de memorie312 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inhacker3.out
2
1 4
3 1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?