問題文

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$個の商品を集めるために必要な最小の金額を出力してください。最後に改行してください。

サンプル

3
6 8
2 9
4 7

13

2
6 2
3 3

11

8
3 13
18 8
3 14
1 18
3 3
18 12
10 18
15 19

169