分数: 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 球必须被移除。