AT_codequeen2026_c 王冠づくり

公主高桥正在制作一顶将在加冕仪式上佩戴的王冠。 王冠上有 $K$ 个装饰宝石的位置，这些位置呈圆形排列。同时，共有 $N$ 个宝石，第 $i$ 个宝石的颜色为 $C_i$，价值为 $V_i$。 你需要从 $N$ 个宝石中选择 $K$ 个不同的宝石，每个位置各放置一个。为了美观，必须遵循以下规则： - 相邻的位置不能放置颜色相同的宝石。 请你求出在满足条件的情况下，可以获得的宝石价值总和的最大值。如果不存在满足条件的放置方法，则输出 $-1$。

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

请输出能够获得的最大价值总和。如果不存在满足条件的放置方法，则输出 $-1$。

### 样例解释 1 若依次选取第 $1,2,3,4$ 个宝石依次放置，则依次（颜色，价值）为 $(1,10),(2,8),(1,7),(3,5)$。此时，价值总和为 $30$。 ### 样例解释 2 无法找到满足条件的方法，将 $5$ 个宝石放在王冠上。请注意王冠为圆形。 ### 约束条件 - $3 \le K \le N \le 2 \times 10^5$ - $1 \le C_i \le N$ - $1 \le V_i \le 10^9$ - 所有输入均为整数。 由 ChatGPT 5 翻译