시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 8 7 7 87.500%

문제

JOI 君は,携帯電話に取り付けるためのストラップを N 個持っている.ストラップには 1 から N までの 番号が付けられている.JOI 君は,これらのストラップのうちいくつかを携帯電話に取り付けようとして いる.

JOI 君の持っているストラップは少し変わっていて,いくつかのストラップには,他のストラップを取 り付けるための端子が何個か付いている.それぞれのストラップは,携帯電話に直接取り付けるか,ある いは他のストラップの端子に取り付けることができる.携帯電話に直接取り付けられるストラップは 1 個 までである.

また,それぞれのストラップには,取り付けたときに得られる嬉しさが決まっている.この嬉しさは 1 つの整数で表される.JOI 君が嫌いなストラップもあり,その場合は嬉しさは負の値になる.

JOI 君は,携帯電話につながっているストラップの嬉しさの総和を最大化したい.ただし,必ずしもす べての端子にストラップが取り付けられている必要はなく,ストラップを 1 つも取り付けなくてもかまわ ない.

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

입력

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

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

출력

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

제한

  • 1 ≤ N ≤ 2 000.
  • 0 ≤ Ai ≤ N (1 ≤ i ≤ N).
  • −1 000 000 ≤ Bi ≤ 1 000 000 (1 ≤ i ≤ N).

예제 입력 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

예제 출력 3

43417