← 返回题目列表

AtCoder · joig2022_e

E. EGOI展览

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI博物馆有N 图片以水平行显示。博物馆里展出的画作 有 M 类型,1 它们的编号最大为 M 。从左边开始 图片类型 i 番目 (1 \leqq i \leqq N) 是 A_i 的值为 V_i 。 在在这里,V_i 也可以是负数。

“Egoi Exhibition 2022”计划下个月在JOI博物馆举办,预计会有很多参观者,所以我们想让它看起来不错。因此,策展人李惠决定移除一些画作,以免相邻的画作属于同一类型。

另一方面,为了提高声誉,我们希望尽可能增加剩余画作的总价值。

图片数量、图片类型数量、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 点)没有额外的限制。 在

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为该子作业的正确结果。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是此作业的所有提交内容的最高分。 在

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

N
M
A_1 V_1
A_2 V_2
\vdots
A_N V_N

出力

剩余图片的值的最大可能总和被打印到标准输出。 1 行。 例如,在


入力例 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 满足约束。