17741번 - 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)．