003 - ストラップ (Straps)

問題

　JOI 君は，携帯電話に取り付けるためのストラップを N 個持っている．ストラップには 1 から N までの番号が付けられている．JOI 君は，これらのストラップのうちいくつかを携帯電話に取り付けようとしている．
　JOI 君の持っているストラップは少し変わっていて，いくつかのストラップには，他のストラップを取り付けるための端子が何個か付いている．それぞれのストラップは，携帯電話に直接取り付けるか，あるいは他のストラップの端子に取り付けることができる．携帯電話に直接取り付けられるストラップは 1 個までである．
　また，それぞれのストラップには，取り付けたときに得られる嬉しさが決まっている．この嬉しさは 1 つの整数で表される．JOI 君が嫌いなストラップもあり，その場合は嬉しさは負の値になる．
　JOI 君は，携帯電話につながっているストラップの嬉しさの総和を最大化したい．ただし，必ずしもすべての端子にストラップが取り付けられている必要はなく，ストラップを 1 つも取り付けなくてもかまわない．

課題

　JOI 君の持っている N 個のストラップの情報が与えられる．適切にストラップを取り付けたとき，携帯電話につながっているストラップの嬉しさの総和の最大値を求めるプログラムを作成せよ．

入力

　標準入力から以下のデータを読み込め．

• 1 行目には，整数 N が書かれている．N はストラップの個数を表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 A_i, B_i が空白を区切りとして書かれている．これはストラップ i には端子が A_i 個あり，そのストラップを取り付けたときの嬉しさが B_i であることを表す．

出力

　標準出力に，携帯電話につながっているストラップの嬉しさの総和の最大値を表す整数を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

• 1 ≤ N ≤ 2 000．
• 0 ≤ A_i ≤ N (1 ≤ i ≤ N)．
• -1 000 000 ≤ B_i ≤ 1 000 000 (1 ≤ i ≤ N)．

小課題

小課題 1 [5 点]

• N ≤ 15 を満たす．

小課題 2 [5 点]

• B_i ≥ 0 (1 ≤ i ≤ N) を満たす．

小課題 3 [45 点]

• A_i ≤ 15 (1 ≤ i ≤ N) を満たす．

小課題 4 [45 点]

　追加の制限はない．

入出力例

入力例　1

5
0 4
2 -2
1 -1
0 1
0 3

出力例 1

5

　この入力の場合，次のようにストラップを取り付けると嬉しさの総和は 5 となり，これが最大となる．

• ストラップ 2 を，携帯電話に直接取り付ける．
• ストラップ 1 を，ストラップ 2 の端子に取り付ける．
• ストラップ 5 を，ストラップ 2 の端子に取り付ける．

入力例　2

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

出力例 2

0

　この入力の場合，どのストラップの嬉しさも 0 未満である．よって，ストラップを 1 つも取り付けない場合に嬉しさの総和が最大となる．

入力例　3

15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925

出力例 2

43417