彩色子序列

题目描述

有 $N$ 个球排成一排。

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

高桥君想从这排球中恰好移除 $K$ 个球,使得在不改变剩余球顺序的情况下,剩余球中相邻两个球的颜色互不相同。 此外,在该条件下,他想让剩余球的总价值尽量大。

请判断高桥君是否能够通过移除 $K$ 个球,使得剩余球中相邻两个球的颜色互不相同。如果可以,请输出剩余球总价值的最大值。

输入格式

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

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

输出格式

如果高桥君能够通过移除 $K$ 个球,使得剩余球中相邻两个球的颜色互不相同,则以整数形式输出剩余球总价值的最大值。 否则,输出 $-1$。

样例

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

10

移除从左数第 $3$ 个和第 $5$ 个球后,剩余球的颜色从左到右为 $1, 3, 1$,相邻两个球的颜色互不相同,满足条件。

剩余球的总价值为 $V_1+V_2+V_4=1+5+4=10$。

从五个球中移除两个球使得相邻颜色互不相同还有其他方法,但移除第 $3$ 个和第 $5$ 个球时剩余球总价值最大。

因此输出 $10$。

3 1
1 10
1 10
1 10

-1

无论移除哪个球,颜色为 $1$ 的球都会相邻,因此输出 $-1$。

3 1
1 1
2 2
3 3

5

注意必须恰好移除 $K$ 个球。

数据范围

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