日本情報オリンピック 第2回 女性部門

2022年1月24日
情報オリンピック日本委員会

問題文

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

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

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

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

制約

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

小課題

1. (4 点) M = 1，N ≦ 15，V_i ≧ 1 (1 ≦ i ≦ N)．
2. (17 点) V_i ≧ 1 (1 ≦ i ≦ N)．
3. (21 点) N ≦ 15．
4. (27 点) N ≦ 100．
5. (19 点) M ≦ 100．
6. (12 点) 追加の制約はない．

採点に関する注意

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

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる．
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 番目の絵を残すのが最適である．

この入力例は小課題 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 の制約を満たす．