Colorful Subsequence

题目描述

有 $N$ 个球排成一行。
从左数第 $i$ 个球的颜色为 $C_i$，价值为 $V_i$。 Takahashi 想要 恰好 移除这行中的 $K$ 个球，使得在不改变剩余球相对顺序的情况下，剩下的球中任意相邻的两个球颜色都不相同。 另外，在满足该条件的前提下，他想要使剩余球的总价值最大化。 判断 Takahashi 是否可以移除 $K$ 个球，使得剩下的行中任意相邻的两个球颜色都不相同。如果可以，求剩余球价值的最大可能值。

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $C_1$ $V_1$ $C_2$ $V_2$ $\vdots$ $C_N$ $V_N$

输出格式

如果 Takahashi 可以移除 $K$ 个球，使得剩下的行中任意相邻的两个球颜色都不相同，则输出剩余球的最大可能总价值（整数）。 否则，输出 $-1$。

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

10

3 1
1 10
1 10
1 10

-1

3 1
1 1
2 2
3 3

5

提示

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$ 所有输入值均为整数。移除从左数第 $3$ 个和第 $5$ 个球后，剩下的球从左到右的颜色为 $1, 3, 1$，因此相邻的球颜色两两不同，满足条件。
剩余球的总价值为 $V_1+V_2+V_4=1+5+4=10$.
还有其他方法可以从五个球中移除两个球，使得相邻球颜色不同，但当移除第 $3$ 个和第 $5$ 个球时剩余球的总价值最大。 因此，输出 $10$.
无论如何移除一个球，颜色为 $1$ 的球最终都会相邻在一起。
因此，输出 $-1$.
注意必须恰好移除 $K$ 个球。

标签: AtCoder|abc345E

来源

AtCoder|abc345E