7270번 - Keleiviai 다국어

문제

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 – noro pildymas daug laiko neužtrunka;
• Palydovė pradeda skrydį stovėdama ties pirmąja eile;
• Palydovė turi pabaigti skrydį stovėdama ties pirmąja eile.

입력

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).

출력

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.

제한

• 1 ≤ N ≤ 100 000
• 1 ≤ a_i, b_i ≤ 1 000 000

힌트