103454: [Atcoder]ABC345 E - Colorful Subsequence

Problem Statement

There are $N$ balls lined up in a row.
The $i$-th ball from the left is of color $C_i$ and has a value of $V_i$.

Takahashi wants to remove exactly $K$ balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.

Determine if Takahashi can remove $K$ balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$C_1$ $V_1$
$C_2$ $V_2$
$\vdots$
$C_N$ $V_N$

Output

If Takahashi can remove $K$ balls so that no two adjacent balls in the remaining row have the same color, print the maximum possible total value of the remaining balls as an integer. Otherwise, print $-1$.

Sample Input 1

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

Sample Output 1

10

After removing the $3$-rd and $5$-th balls from the left, the remaining balls are of colors $1, 3, 1$ from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is $V_1+V_2+V_4=1+5+4=10$.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the $3$-rd and $5$-th balls.

Hence, print $10$.

Sample Input 2

3 1
1 10
1 10
1 10

Sample Output 2

-1

No matter how you remove one ball, balls of color $1$ will end up next to each other.
Hence, print $-1$.

Sample Input 3

3 1
1 1
2 2
3 3

Sample Output 3

5

Note that exactly $K$ balls must be removed.

问题描述

有一行排成一行的$N$个球。

从左数第$i$个球的颜色是$C_i$，价值是$V_i$。

Takahashi想要从这一行中移除恰好 $K$个球，使得重新排列剩下的球时，没有两个相邻的球颜色相同。此外，在这种情况下，他希望最大化剩下球的总价值。

确定Takahashi是否可以移除$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$

输出

如果Takahashi可以移除$K$个球，使得剩下的一行中没有两个相邻的球颜色相同，将剩下球的最大可能总价值作为一个整数输出。否则，输出$-1$。

样例输入1

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

样例输出1

10

从左数移除第3个和第5个球后，剩下的球从左到右的颜色为$1, 3, 1$，因此没有两个相邻的球颜色相同，满足条件。
剩下球的总价值为$V_1+V_2+V_4=1+5+4=10$。
有其他方法从五个球中移除两个球，使得没有两个相邻的球颜色相同，但是当移除第3个和第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$个球。