エゴイ展 (EGOI Exhibition)

問題文

JOI 美術館には，N 枚の絵が横一列に飾られている．美術館に展示されている絵には M 個の種類があり，1 から M までの番号が付けられている．左から i 番目 (1 ≦ i ≦ N) の絵の種類は A_i であり，価値は V_i である．ここで，V_i は負の数になることもある．

来月，JOI 美術館では「エゴイ展 2022」が開催予定であり，多くの来客が見込まれるため，見栄えを良くしたい．そこで館長の理恵さんは，隣り合う絵が同じ種類にならないように，いくつかの絵を撤去することにした．

一方で，評判を高めるため，残された絵の価値の合計をできるだけ大きくしたい．

絵の枚数，絵の種類数，N 枚の絵の情報が与えられたとき，残された絵の価値の合計として考えられる最大値を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 150000．
• 1 ≦ M ≦ N．
• 1 ≦ A_i ≦ M (1 ≦ i ≦ N)．
• - 10000 ≦ V_i ≦ 10000 (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．
N
M
A₁ V₁
A₂ V₂
:
A_N V_N

出力

標準出力に，残された絵の価値の合計として考えられる最大値を 1 行で出力せよ．

入出力例

入力例 1

3
1
1 107
1 123
1 100

出力例 1

123

左から 2 番目の絵のみを残した場合，価値の合計は V₂ = 123 となる．

入力例 2

4
3
1 204
2 168
2 277
1 219

出力例 2

700

左から 1, 3, 4 番目の絵を残すのが最適である．

入力例 3

3
2
1 5
2 -1
1 5

出力例 3

9

すべての絵を残すのが最適である．

入力例 4

6
4
1 -123
2 -123
3 -123
4 -123
4 -123
3 -123

出力例 4

0

絵を 1 枚も残さないのが最適である．

入力例 5

30
4
2 -1358
4 -1405
4 2003
3 -1148
2 -1527
2 -2015
4 -2910
1 2133
2 2185
1 2249
3 1058
1 -1907
2 -3190
1 -2701
3 -2640
1 1685
3 1855
4 2398
3 -3158
2 1947
3 2947
2 -2197
4 1398
2 -3011
4 -1971
1 -2829
1 3094
2 2704
4 -2592
3 2910

出力例 5

30566

---