Amerikan dağları

Anna əyləncə parkında işləyir və yeni "Amerikan dağları" attraksionunu layihələndirir. Bu attraksion, xüsusi bir qatarın hərəkət edəcəyi bir marşrutdan ibarətdir. Qatarın uzunluğunu sıfır hesab edirik. Anna artıq sürətə təsir edən $n$ xüsusi bölməni (rahatlıq üçün $0$-dan $n-1$-ə qədər nömrələnmiş) layihələndirib: yüksəlişlər, kəskin əyləclər və s. İndi o, bu bölmələri yollarla birləşdirərək attraksionun son planını hazırlamalıdır.

Hər bir $i$ üçün ($0$-dan $n-1$-ə qədər, daxil olmaqla), xüsusi bölmə $i$ iki dəyərlə xarakterizə olunur:

• bu bölməyə daxil olarkən sürət məhdudiyyəti var: qatarın bölməyə daxil olarkən sürəti $s_i$ km/saat-dan az və ya bərabər olmalıdır,

• bölmədən çıxarkən qatarın sürəti, qatarın bölməyə hansı sürətlə daxil olmasından asılı olmayaraq, dəqiq olaraq $t_i$ km/saat olur.

Nəticədə attraksionun planı, bütün $n$ xüsusi bölmələrin müəyyən bir ardıcıllıqla qarşılaşdığı vahid bir marşrutdan ibarət olmalıdır. Hər bir $n$ bölmə attraksionun son planına dəqiq bir dəfə daxil olmalıdır.

Ardıcıl bölmələr arasında birləşdirici yollar çəkilməlidir. Anna bölmələri attraksion marşrutu boyunca hansı ardıcıllıqla yerləşdirəcəyinə və hər bir birləşdirici yolun uzunluğunu seçməlidir. Hər bir birləşdirici yolun uzunluğu metrlə ölçülür və sıfırdan böyük olmayan tam ədəd olmalıdır (mümkün olduqda sıfır ola bilər).

İki xüsusi bölmə arasında hər bir metr birləşdirici yol qatarı $1$ km/saat yavaşladır. Səyahətin əvvəlində qatar marşrutdakı ilk xüsusi bölməyə $1$ km/saat sürətlə daxil olur.

Attraksionun son planı aşağıdakı tələblərə cavab verməlidir:

• qatar xüsusi bölmələrə daxil olarkən sürət məhdudiyyətini pozmamalıdır;

• qatarın sürəti marşrut boyunca hər hansı bir anda mütləq müsbət olmalıdır.

Sizdən xüsusi bölmələrin ardıcıllığını və onların arasındakı birləşdirici yolların uzunluqlarını elə seçmək tələb olunur ki, göstərilən tələblər yerinə yetirilsin və birləşdirici yolların ümumi uzunluğu mümkün qədər az olsun.

Giriş verilənləri

Birinci sətir $n(2\le n\le 2\cdot 10^5)$ ədədini ehtiva edir. Növbəti $n$ sətirin hər biri $s_i$ və $t_i(1\le i\le n,1\le s_i,t_i\le 10^9)$ ədədlərini ehtiva edir.

Çıxış verilənləri

Xüsusi bölmələr arasında bütün birləşdirici yolların minimal mümkün ümumi uzunluğunu çap edin.

Nümunələr