まず、要素数 \(K\) の色の多重集合 \(S\) を選んだとき、それを王冠にできる条件を考えます。

この条件は以下のようになります。

• どの色も \(S\) に含まれる個数が \(K/2\) 個以下である。

証明

ある色が $x$ 個使われているとします。同じ色を隣り合わせないためには、その $x$ 個の間にそれぞれ別の色が必要なので、$K-x\geq x$、すなわち $x\leq K/2$ が必要です。

逆に、各色が $K/2$ 個以下であるとします。色ごとにまとめて個数の多い順に並べ、その順に王冠の $1,3,\ldots,K-1,2,4,\ldots,K$ 番目へ配置します。各色は高々 $K/2$ 個なので、同じ色が隣り合うことはありません。したがって、この条件は十分でもあります。

この条件を満たしながら価値を最大化するには、すべての宝石を価値の高い順に見て、その色の宝石をまだ $K/2$ 個選んでいなければ選べばよいです。

証明

各色から使える宝石は高々 $K/2$ 個なので、各色について価値が上位 $K/2$ 個に入らない宝石は最適解に必要ありません。

これらを除くと、残った宝石はどの色も高々 $K/2$ 個です。したがって、その中から価値の高いものを $K$ 個選べば最適です。

これは、すべての宝石を価値の高い順に見て、各色から高々 $K/2$ 個まで選ぶことと同じです。

---

実装例

from collections import defaultdict

n, k = map(int, input().split())
a = []

for _ in range(n):
    c, v = map(int, input().split())
    a.append((v, c))

a.sort(reverse=True)

cnt = defaultdict(int)
ans = 0
ch = 0

for v, c in a:
    if cnt[c] >= k // 2:
        continue

    cnt[c] += 1
    ans += v
    ch += 1

    if ch == k:
        break

print(ans if ch == k else -1)