AT_codequeen2026_c 王冠づくり

プリンセスの高橋さんは、戴冠式でかぶる王冠を作っています。 王冠には、宝石を取り付ける場所が円形に $ K $ 個並んでいます。また、宝石は $ N $ 個あり、 $ i $ 番目の宝石の色は $ C_i $ 、価値は $ V_i $ です。 $ N $ 個の宝石から異なる $ K $ 個の宝石を選び、それぞれの場所に $ 1 $ つずつ取り付けます。ただし、美しさのために、以下のルールを守らなければなりません。 - 隣り合う場所に、同じ色の宝石を取り付けてはいけない 取り付けた宝石の価値の合計として考えられる最大値を求めてください。ただし、条件を満たす取り付け方が存在しない場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C_1 $ $ V_1 $ $ C_2 $ $ V_2 $ $ \vdots $ $ C_N $ $ V_N $

取り付けた宝石の価値の合計として考えられる最大値を出力せよ。ただし、条件を満たす取り付け方が存在しない場合は $ -1 $ を出力せよ。

### Sample Explanation 1 $ 1, 2, 3, 4 $ 番目の宝石を順に取り付けることにすると $ ( $ 色, 価値 $ ) $ が $ (1, 10),(2, 8),(1, 7),(3, 5) $ の順に並びます。このとき、価値の合計は $ 30 $ です。 ### Sample Explanation 2 条件を満たすように $ 5 $ 個の宝石を取り付けることはできません。王冠は円形であることに注意をしてください。 ### Constraints - $ 3 \le K \le N \le 2 \times 10 ^ 5 $ - $ 1 \le C_i \le N $ - $ 1 \le V_i \le 10^9 $ - 入力はすべて整数である