No.860 Shopping
タグ : / 解いたユーザー数 79
作問者 :
nmnmnmnmnmnmnm
/ テスター :
testestest
Problem Statement
A plans to buy $N$ items at Store B.The $i$-th item has a price $C_i$ and a packing cost $D_i$.
The order of purchase is fixed: he always buys the items in increasing order of index.
The following rules apply when shopping at Store B.
・Purchasing an item costs its price, for each item.
・For every item bought second or later within a single day, that item's packing cost is added.
・If one or more items are bought within a day, a fee is charged. The fee is equal to the price of the cheapest item bought that day.
A noticed that splitting the purchases across different days may lower the total purchase cost.
What is the minimum cost A pays when he makes an optimal purchase plan?
Input
$N$
$C_0$ $D_0$
$C_1$ $D_1$
$\vdots$
$C_{N-1}$ $D_{N-1}$
$N$ is the number of items to purchase. $N$ is a positive integer. $1 \le N \le 100000=10^5$.
$C_i$ is the price of the $i$-th item to purchase. $C_i$ is a positive integer. $1 \le C_i \le 1000000000=10^9$.
$D_i$ is the packing cost of the $i$-th item to purchase. $D_i$ is a positive integer. $1 \le D_i \le 1000000000=10^9$.
Output
Output the answer on one line.
Print a newline at the end.
Sample
Sample 1
Input
3 20 5 10 3 30 12
Output
85
The optimal way is to buy all 3 items in one day.
Item 0 has a price of 20.
Item 1 has a price of 10, and a packing cost of 3 is added.
Item 2 has a price of 30, and a packing cost of 12 is added.
The fee for this day is 10, equal to the price of item 1, the cheapest.
The purchase cost in this case is 20+(10+3)+(30+12)+10=85.
Sample 2
Input
2 10 30 15 20
Output
50
The optimal way is to buy the items one at a time over 2 days.
Item 0 has a price of 10.
The fee for this day is 10, equal to the price of item 0, the cheapest.
Item 1 has a price of 15.
The fee for this day is 15, equal to the price of item 1, the cheapest.
The purchase cost in this case is 10+10+15+15=50.
Incidentally, buying them all together in one day would cost 55.
Sample 3
Input
10 120 63 65 31 58 80 61 59 80 75 110 63 58 12 91 80 30 30 71 53
Output
1203
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。