SPOJ in Armenian

Շուտով բամբուկը կսկսի աճել։ Բամբուկի վերավաճառողները ընդունում են ցանկացած քանակի բամբուկ ամեն օր ճիշտ կեսօրին։ Սակայն բամբուկի գինը օրեցօր փոփոխվում է։ Մեզ հաջողվել է իմանալ, թե ի՞նչ գնով են վերավաճառողներն ընդունելու բամբուկը։ Բացի այդ, մենք ճշգրիտ գիտենք, թե ամեն օր բամբուկը քանի մետրով է երկարելու (այդ մեծությունն էլ է փոփոխական)։

Ցանկացած օր կարելի է ամբողջ բամբուկը կտրել և հանձնել վաճառքի, կամ կարելի է թողնել, որ էլի աճի։ Կտրելուց հետո բամբուկը նորից շարունակում է աճել։

Պահանջվում է գտնել, թե բամբուկի վաճառքից ամենաշատը որքան եկամուտ է կարելի ստանալ։ Ամենասկզբում բամբուկի երկարությունը զրո է։ Բամբուկի աճը տևում է ճիշտ N օր։

Մուտքը

Առաջին տողում տրված է N բնական թիվը, 1<=N<=100000։ Հաջորդ N տողերից յուրաքանչյուրը պարունակում է մի բացակով իրարից անջատված երկու բնական թվեր՝ տվյալ օրը բամբուկի մի մետրի գինը և, թե որքանով է աճել բամբուկը վերջին օրվա ընթացքում։ (i+1)-րդ տողում տրված տվյալները վերաբերվում են i-րդ օրվան։

Ելքը

Պետք է արտածել մի ամբողջ ոչ բացասական թիվ՝ բամբուկի վաճառքից ամենամեծ հնարավոր եկամուտի չափը։ Երաշխավորվում է, որ պատասխանը չի գերազանցի 2⁶³-1 թիվը։

Օրինակ

Մուտքը.
8
2 7
4 1
3 3
5 5
2 4
5 2
4 7
1 1

Ելքը.
139