24424번 - エゴイ展 (EGOI Exhibition) 서브태스크다국어

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

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

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

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

入力は以下の形式で標準入力から与えられる．

N
M
A1 V1
A2 V2
:
AN VN

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

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