JAG Practice Contest

時間制限 : 8 sec, メモリ制限 : 262144 KB

JAG 模擬予選練習会

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

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

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

Input

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

N M
d1 v1
...
dN vN

データセットの 1 行目には,問題ストックの数を表す整数 N と,難易度の最大値 M が空白区切りで与えられる. これらの数は 1 ≤ M ≤ N ≤ 100 を満たす. 続く N 行の内 i 行目には,問題 i の難易度と推薦度を表す整数 divi が空白区切りで与えられる. これらの数は 1 ≤ di ≤ M および 0 ≤ vi ≤ 100 を満たす. また,各 1 ≤ j ≤ M について,di = 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

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2017, 2017-07-02
http://acm-icpc.aitea.net/