AT_abc345_e [ABC345E] Colorful Subsequence

有 $N$ 个球排成一列。 从左到右第 $i$ 个球的颜色为 $C_i$，价值为 $V_i$。 高桥君想要从这列球中**恰好**移除 $K$ 个球，使得剩下的球按照原本的顺序排列时，相同颜色的球不会相邻。同时，在满足上述条件的前提下，他希望剩下球的价值总和尽可能大。 请判断高桥君是否能够通过移除 $K$ 个球，使得剩下的球中没有相邻的球颜色相同。如果可以，请求出剩下球的价值总和的最大可能值；如果不可以，请输出 $-1$。

输入按以下格式从标准输入读入。 > $N$ $K$ > $C_1$ $V_1$ > $C_2$ $V_2$ > $\vdots$ > $C_N$ $V_N$

如果高桥君能够移除 $K$ 个球，使得剩下的球中没有相邻的球颜色相同，则输出剩下球的最大价值总和（一个整数）。如果无法做到，则输出 $-1$。

## 限制条件 - $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$ - 输入均为整数 ## 样例解释 1 如果移除第 $3$、$5$ 个球，剩下的球从左到右颜色为 $1,3,1$，因此任意相邻的两个球颜色都不同，满足条件。此时，剩下球的价值和为 $V_1+V_2+V_4=1+5+4=10$。 除此之外，从 $5$ 个球中移除 $2$ 个球且满足相邻颜色不同的方法还有其他，但移除第 $3$、$5$ 个球时剩下球的价值和最大。因此输出 $10$。 ## 样例解释 2 无论移除哪一个球，颜色为 $1$ 的球都会相邻。因此输出 $-1$。 ## 样例解释 3 请注意，必须**恰好**移除 $K$ 个球。 由 ChatGPT 4.1 翻译