問題文

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

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

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

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

制約

• 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 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

3
1
1 107
1 123
1 100

出力例 1

123

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

この入力例はすべての小課題の制約を満たす．

入力例 2

4
3
1 204
2 168
2 277
1 219

出力例 2

700

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

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．

入力例 3

3
2
1 5
2 -1
1 5

出力例 3

9

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

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 4

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

出力例 4

0

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

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 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

この入力例は小課題 4, 5, 6 の制約を満たす．