Բամբուկի ծառերի վաճառքը
Դուք ունեք մի բամբուկի ծառ, որը տարբեր օրերին աճում է տարբեր արագությամբ։ Դուք ցանկանում եք գումար աշխատել՝ կտրելով ու վաճառելով այդ բամբուկը (խոսքը գնում է ամբողջ ծառը կտրելու մասին, սակայն այն շարունակելու է աճել նույնիսկ կտրելուց հետո):
Բամբուկը սկզբում (առաջին օրը) ունի 0 երկարություն և աճում է ընդհանուր առմամբ
n օր։ Դուք նախապես գիտեք, թե յուրաքանչյուր օրվա համար մեկ մետր բամբուկին ինչ արժե, ինչպես նաև որքանով է ծառը աճելու նախորդ գիշերը, մինչև վաճառելու պահը։
Ամեն օրվա համար դուք կամ կտրում եք ամբողջ ծառը (որը, հետագայում շարունակում է աճել) և վաճառում եք, կամ թողնում եք, որ այն շարունակի աճել։ Պետք է պարզել, թե ինչքան առավելագույն գումար կարող եք աշխատել։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ), որը ցույց է տալիս օրերի քանակը։Հաջորդ
n տողերում տրված են երկու բացատով բաժանված ամբողջ թվեր (, ) (1 ≤ , ≤ ), որտեղ -ն ցույց է տալիս, թե բամբուկը քանի մետրով է աճում վաճառքից անմիջապես առաջ տեղի ունեցած գիշերը, իսկ -ն՝ մեկ մետր բամբուկի արժեքը i-րդ օրը։Ելք
Ծրագիրը պետք է տպի առավելագույն գումարը, որը կարելի է ստանալ բամբուկը աճեցնելով և վաճառելով։ Երաշխավորված է, որ պատասխանը չի գերազանցում -ը։
Օրինակներ
Մուտք | Ելք |
8
7 2
1 4
3 3
5 5
4 2
2 5
7 4
1 1 | 139 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB