[ABC345] E - Colorful Subsequence

E - Colorful Subsequence

Time Limit: 5 sec / Memory Limit: 1024 MB

题面

有 个球排成一行。
从左起第 个球的颜色为 ，价值为 。

高桥想要移除恰好 个球，使得在不改变剩余球的顺序的情况下，剩下的球中相邻的球颜色不相同。此外，在这种情况下，他希望最大化剩余球的总价值。

确定高桥是否可以移除 个球，使得剩余行中相邻的球颜色不相同。如果可能，找到剩余球的最大可能总价值。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出：

输出

如果高桥可以移除 个球，使得剩余行中相邻的球颜色不相同，则输出剩余球的最大可能总价值（作为整数）。否则，输出 。

---

输入样例 1

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

输出样例 1

10

移除从左起第 和第 个球后，剩下的球颜色依次为 ，因此相邻的球颜色不相同，满足条件。
剩余球的总价值为 。
还有其他方法可以移除五个球中的两个，使得剩下的相邻球颜色不同，但当移除第 和第 个球时，剩余球的总价值最大。

因此，输出 。

---

输入样例 2

3 1
1 10
1 10
1 10

输出样例 2

-1

无论移除哪一个球，颜色为 的球都会相邻。
因此，输出 。

---

输入样例 3

3 1
1 1
2 2
3 3

输出样例 3

5

需要移除恰好 个球。