No.860 買い物
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 :
nmnmnmnmnmnmnm
/ テスター :
testestest
タグ : / 解いたユーザー数 72
作問者 :
nmnmnmnmnmnmnm
/ テスター :
testestest
問題文最終更新日: 2019-05-12 17:38:57
問題文
A君はB商店で$N$個の商品を買う計画をしています。$i$番目の商品には価格$C_i$と梱包費用$D_i$があります。
商品を買う順番は決めており、かならず小さい番目の商品から買います。
B商店で買い物をするときには次のようなルールがあります。
・商品を購入すると商品ごとに価格の費用がかかります。
・1日のうちで2つ目以降に買う商品についてはすべてその商品の梱包費用が追加されます。
・1日のうちで1つ以上の商品を買うと手数料が発生します。手数料はその日に買ったいちばん安い商品の価格と同額です。
A君は商品を買う日を分けることで全体の購入費用が安くなる可能性があることに気づきました。
A君が最適な購入計画を立てたとき支払う最小の費用はいくらか。
入力
$N$
$C_0$ $D_0$
$C_1$ $D_1$
$\vdots$
$C_{N-1}$ $D_{N-1}$
$N$は購入する商品の個数。$N$は正の整数。$1 \le N \le 100000=10^5$。
$C_i$は購入する$i$番目の商品の価格。$C_i$は正の整数。$1 \le C_i \le 1000000000=10^9$。
$D_i$は購入する$i$番目の商品の梱包費用。$D_i$は正の整数。$1 \le D_i \le 1000000000=10^9$。
出力
答えを1行で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 20 5 10 3 30 12
出力
85
最適な買い物は1日で3つの商品を購入します。
0番目の商品は価格が20です。
1番目の商品は価格が10で梱包費用が3追加されます。
2番目の商品は価格が30で梱包費用が12追加されます。
この日の手数料はいちばん安い1番目の商品の価格と同額の10です。
このときの購入費用は20+(10+3)+(30+12)+10=85です。
サンプル2
入力
2 10 30 15 20
出力
50
最適な買い物は1つずつの商品を2日に分けて購入します。
0番目の商品は価格が10です。
この日の手数料はいちばん安い0番目の商品と同額の10です。
1番目の商品は価格が15です。
この日の手数料はいちばん安い1番目の商品の価格と同額の15です。
このときの購入費用は10+10+15+15=50です。
ちなみに1日でまとめて買ってしまうと費用は55になってしまいます。
サンプル3
入力
10 120 63 65 31 58 80 61 59 80 75 110 63 58 12 91 80 30 30 71 53
出力
1203
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。