AT_joig2022_e エゴイ展 (EGOI Exhibition)

[problemUrl]: https://atcoder.jp/contests/joig2022-open/tasks/joig2022_e JOI 美術館には，$ N $ 枚の絵が横一列に飾られている．美術館に展示されている絵には $ M $ 個の種類があり，$ 1 $ から $ M $ までの番号が付けられている．左から $ i $ 番目 ($ 1\ \leqq\ i\ \leqq\ N $) の絵の種類は $ A_i $ であり，価値は $ V_i $ である．**ここで，$ V_i $ は負の数になることもある．** 来月，JOI 美術館では「エゴイ展 2022」が開催予定であり，多くの来客が見込まれるため，見栄えを良くしたい．そこで館長の理恵さんは，隣り合う絵が同じ種類にならないように，いくつかの絵を撤去することにした． 一方で，評判を高めるため，残された絵の価値の合計をできるだけ大きくしたい． 絵の枚数，絵の種類数，$ N $ 枚の絵の情報が与えられたとき，残された絵の価値の合計として考えられる最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ A_1 $ $ V_1 $ $ A_2 $ $ V_2 $ $ \vdots $ $ A_N $ $ V_N $

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

### 制約 - $ 1\ \leqq\ N\ \leqq\ 150\,000 $． - $ 1\ \leqq\ M\ \leqq\ N $． - $ 1\ \leqq\ A_i\ \leqq\ M $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ -10\,000\ \leqq\ V_i\ \leqq\ 10\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - 入力される値はすべて整数である． ### 小課題 1. ($ 4 $ 点) $ M\ =\ 1 $，$ N\ \leqq\ 15 $，$ V_i\ \geqq\ 1 $ ($ 1\ \leqq\ i\ \leqq\ N $)． 2. ($ 17 $ 点) $ V_i\ \geqq\ 1 $ ($ 1\ \leqq\ i\ \leqq\ N $)． 3. ($ 21 $ 点) $ N\ \leqq\ 15 $． 4. ($ 27 $ 点) $ N\ \leqq\ 100 $． 5. ($ 19 $ 点) $ M\ \leqq\ 100 $． 6. ($ 12 $ 点) 追加の制約はない． ### 採点に関する注意 すべての提出はジャッジシステム上で採点される． 提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる． 各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である． この課題の得点は，**この課題に対するすべての提出の得点の最大値**である． 現在の得点は「提出結果」タブの「自分の得点状況」から確認できる． ### Sample Explanation 1 左から $ 2 $ 番目の絵のみを残した場合，価値の合計は $ V_2\ =\ 123 $ となる． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 2 左から $ 1,\ 3,\ 4 $ 番目の絵を残すのが最適である． この入力例は小課題 $ 2,\ 3,\ 4,\ 5,\ 6 $ の制約を満たす． ### Sample Explanation 3 すべての絵を残すのが最適である． この入力例は小課題 $ 3,\ 4,\ 5,\ 6 $ の制約を満たす． ### Sample Explanation 4 絵を $ 1 $ 枚も残さないのが最適である． この入力例は小課題 $ 3,\ 4,\ 5,\ 6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 4,\ 5,\ 6 $ の制約を満たす．