No.798 コレクション

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 95
作問者 : ikdikd / テスター : 37zigen37zigen
18 ProblemId : 2406 / 出題時の順位表

問題文

yukiくんの住む町に明日新しい店がオープンします。
yukiくんは明日から毎日その店に通い、$1$日に$1$つずつ商品を買うことで店の商品をすべて集めることに決めました。
町にはyukiくんしか住んでいないため、他の人がその店の商品を買うことはありません。

店で扱っている商品は$N$個あり、$i$番目の商品の価格ははじめ$A_i$円です。
ただし商品の価格は$1$日ごとに$B_i$円ずつ上昇していきます。
つまり、商品$i$をオープンから$d$日目に購入するには$A_i+B_i \times d$円が必要になります。
なお、オープン初日についてはオープンから$0$日目と考えます。
また、各商品は在庫が$1$つしか存在せず同じ商品を$2$度購入することはできません。

店ではオープンから経った日数が奇数の日(オープンから$1$日目、$3$日目、$5$日目、...)にキャンペーンを行っています。
キャンペーンが行われている日に商品を買った人は、購入した商品とは別に好きな商品を$1$つだけその商品の価格に関係なく$0$円で購入することができます。

yukiくんは商品を買う順番を工夫して、できるだけ少ない金額で店の商品を全て集めたいと考えています。
最小でいくらあれば$N$個の商品全てを集めることができるでしょうか。

入力

$N$
$A_1\ B_1$
$A_2\ B_2$
$.$
$.$
$A_N\ B_N$

$1$行目に商品の個数$N$が与えられます。
$2$行目から$N$行にわたって商品の情報が与えられます。
そのうち$i$行目には商品$i$のはじめの価格$A_i$および整数$B_i$が空白区切りで与えられます。

制約

  • $1 \le N \le 2000$
  • $1 \le A_i,B_i \le 10^5\ (i=1, 2, \dots, N)$
  • 入力はすべて整数

出力

$N$個の商品を集めるために必要な最小の金額を出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
6 8
2 9
4 7
出力
13

この場合yukiくんの最適な行動は次のようになります。

  • $0$日目:$2+9 \times 0=2$円払って商品$2$を購入する
  • $1$日目:$4+7 \times 1=11$円払って商品$3$を購入する
    • オープンから奇数日目なので、キャンペーンによって無料で商品$1$を購入する
合計で$2+11=13$円払ったので$13$を出力します。
サンプル2
入力
2
6 2
3 3
出力
11

$0$日目に商品$2$を購入し$1$日目に商品$1$を購入するのが最適です。

yukiくんは次のような行動をとれないことに注意してください。

  • $0$日目に商品を購入せず、$1$日目に商品$2$を購入しキャンペーンによって$0$円で商品$1$を購入する
  • $0$日目に商品$2$を購入し、$1$日目にも商品$2$を購入、キャンペーンによって$0$円で商品$1$を購入する
サンプル3
入力
8
3 13
18 8
3 14
1 18
3 3
18 12
10 18
15 19
出力
169

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。