← 返回题目列表

AtCoder · abc345_e

H. 彩色子序列

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

分数: 525 点

问题陈述

有 N 球排成一排。
的 i左边第一个球是彩色的 C_i 的值为 V_i.

高桥想要删除 正是 K 球从这一行开始,以便在不改变顺序的情况下排列剩余的球时,没有两个相邻的球具有相同的颜色。 另外,在这种情况下,他希望最大化该行中剩余球的总价值。

确定高桥是否可以删除 K 球,以便剩余行中没有两个相邻的球具有相同的颜色。如果可能的话,找出剩余球的最大可能总价值。

约束

  • 1\leq K<N\leq 2\times 10^5
  • K\leq 500
  • 1\leq C_i\leq N
  • 1\leq V_i\leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
C_1 V_1
C_2 V_2
\vdots
C_N V_N

输出

如果高桥可以删除 K 球,使得剩余行中没有两个相邻球具有相同的颜色,将剩余球的最大可能总值打印为整数。 否则,打印 -1.


示例输入 1

5 2
1 1
3 5
3 3
1 4
1 2

示例输出 1

10

删除后 3-rd 和 5左数第个球,其余球都是彩色的 1, 3, 1 从左到右,因此没有两个相邻的球具有相同的颜色,满足条件。
剩余球的总价值为 V_1+V_2+V_4=1+5+4=10.
还有其他方法可以从五个球中移除两个球,使得没有两个相邻的球具有相同的颜色,但是移除五个球时剩余球的总价值最大化 3-rd 和 5第一个球。

因此,打印 10.


示例输入 2

3 1
1 10
1 10
1 10

示例输出 2

-1

无论你如何移除一颗球,彩色球 1 最终将彼此相邻。
因此,打印 -1.


示例输入 3

3 1
1 1
2 2
3 3

示例输出 3

5

请注意,确切地说 K 球必须被移除。