0748 - JAG 模擬予選練習会

時間制限 8 秒 / メモリ制限 512 MB / 得点 10 / Writer root / x 12 / 統計 /


TLE
8sec
MLE
512MB
得点
10

問題

ACM-ICPC OB/OGの会 (Japanese Alumni Group; JAG) には模擬コンテストで出題する問題のストックが $N$ 問あり,それぞれの問題は $1$ から $N$ の整数で番号付けられている. それぞれの問題について難易度評価と推薦投票が行われており,問題 $i$ の難易度は $d_i$ で,推薦度は $v_i$ である. また,難易度の最大値は $M$ である.

次のコンテストでは,難易度 $1$ から $M$ の問題をそれぞれ $1$ 問ずつ,計 $M$ 問出題する予定である. コンテストのクオリティを上げるために推薦度の合計が最大になるように問題を選定したい. ただし,JAG の作問力はすさまじいので,各難易度の問題が最低でも $1$ 問以上ずつあると仮定してよい.

あなたの仕事は,条件を満たすように問題を選定したときの推薦度の和の最大値を求めるプログラムを作成することである.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

$N$ $M$
$d_1$ $v_1$
...
$d_N$ $v_N$

データセットの $1$ 行目には,問題ストックの数を表す整数 $N$ と,難易度の最大値 $M$ が空白区切りで与えられる. これらの数は $1 \le M \le N \le 100$ を満たす. 続く $N$ 行の内 $i$ 行目には,問題 $i$ の難易度と推薦度を表す整数 $d_i$ と $v_i$ が空白区切りで与えられる. これらの数は $1 \le d_i \le M$ および $0 \le v_i \le 100$ を満たす. また,各 $1 \le j \le M$ について,$d_i = j$ となる $i$ が $1$ つ以上存在することが保証される.

入力の終わりは空白で区切られた $2$ つのゼロで表される. また,データセットの数は $50$ を超えない.

Output

各データセットについて,各難易度から $1$ 問ずつ出題するときの,出題する問題の推薦度の和の最大値を $1$ 行に出力せよ.


Sample Input

5 3
1 1
2 3
3 2
3 5
2 1
4 2
1 7
2 1
1 3
1 5
6 1
1 3
1 2
1 8
1 2
1 7
1 6
20 9
4 10
2 4
5 3
6 6
6 3
7 4
8 10
4 6
7 5
1 8
5 7
1 5
6 6
9 9
5 8
6 7
1 4
6 4
7 10
3 5
19 6
4 1
6 5
5 10
1 10
3 10
4 6
2 3
5 4
2 10
1 8
3 4
3 1
5 4
1 10
1 3
5 6
5 2
1 10
2 3
0 0

サンプルのデータセットは $5$ つあり,順に
$1$ 行目から $6$ 行目までが $1$ つ目 $(N = 5, M = 3)$ のテストケース,
$7$ 行目から $11$ 行目までが $2$ つ目 $(N = 4, M = 2)$ のテストケース,
$12$ 行目から $18$ 行目までが $3$ つ目 $(N = 6, M = 1)$ のテストケース,
$19$ 行目から $39$ 行目までが $4$ つ目 $(N = 20, M = 9)$ のテストケース,
$40$ 行目から $59$ 行目までが $5$ つ目 $(N = 19, M = 6)$ のテストケースをそれぞれ表す.

Output for Sample Input

9
8
8
71
51