Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e1_keleiviai_vyr.in

Rezultatų failas: lmio_2018_3e1_keleiviai_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Keleiviai

Užduotis

Kiekvieną savaitgalį iš Bitlandijos į Vilnių skrenda lėktuvas. Šio lėktuvo keleiviai yra labai įnoringi ir sudaro daug problemų įgulai: nuolatos prašo tai arbatos, tai pagalvėlės ir pan.

Įgulai bandant išpildyti visus norus, lėktuvą kartais tenka užlaikyti ore virš Vilniaus! Žinoma, tai nepatinka Bitlandijos oro linijoms, tad jos nusprendė nuo šiol prašyti savo keleivių iš anksto pateikti sąrašą ko ir kada jie prašys.

Turėdami šį sąrašą Jūs turėsite rasti, kiek laiko skrydžių palydovė užtruks pildydama visus norus, jei savo laiką ji planuos optimaliai.

Jums taip pat žinoma, kad:

  • Perėjimas tarp lėktuvo eilių užtrunka 1 min;
  • Palydovė geba pildyti norus labai greitai;
  • Palydovė pradeda skrydį stovėdama ties pirmąja eile;
  • Palydovė turi pabaigti skrydį stovėdama ties pirmąja eile.

Pradiniai duomenys

Pirmojoje eilutėje pateiktas norų skaičius N.

Tolimesnėse N eilučių pateikta po vieną skaičių a_i,b_i porą, aprašančią vieną keleivio norą. Čia a_i – eilės, kurioje sėdi keleivis, numeris, o b_i – anksčiausias laiko momentas, kai i-tasis noras bus pateiktas (jį išpildyti galima ir vėliau).

Rezultatai

Jums reikia išvesti vieną skaičių – per kiek mažiausiai minučių palydovei pavyks įvykdyti visus norus ir sugrįžti iki pirmosios eilės.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
3
2 5
3 3
6 9
 
14
 
vienas galimų aptarnavimo scenarijų: 
Palydovė pradeda skrydį stovėdama ties pirmąja eile, laiko momentu 0 min.
Palydovė nueina iki 3 eilės, tai jai užtrunka 2 min.
Ten palaukia 1 min. ir iš pildo ką tik pateiktą antrąjį pageidavimą.
Palydovė pereina į 2 eilę.
Ten palaukia 1min. ir išpildo pirmąjį norą.
Tada palydovė nuskuba iki 6 eilės. Ten ji nueina laiko momentu 9 min. ir išpildo trečiąjį norą.
Galiausiai palydovė nuskuba iki pirmosios eilės ir baigia savo darbą.
 
3
1 1
1 1
1 5
 
5
 







Ribojimai


1\\leqN\\leq100000


1\\leqa_i,b_i\\leq1000000