問題文

プリンセスの高橋さんは、戴冠式でかぶる王冠を作っています。

王冠には、宝石を取り付ける場所が円形に K 個並んでいます。また、宝石は N 個あり、i 番目の宝石の色は C_i、価値は V_i です。

N 個の宝石から異なる K 個の宝石を選び、それぞれの場所に 1 つずつ取り付けます。ただし、美しさのために、以下のルールを守らなければなりません。

• 隣り合う場所に、同じ色の宝石を取り付けてはいけない

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

制約

• 3 \le K \le N \le 2 \times 10 ^ 5
• 1 \le C_i \le N
• 1 \le V_i \le 10^9
• 入力はすべて整数である

入力例 1

5 4
1 10
2 8
1 7
3 5
2 1

出力例 1

30

1, 2, 3, 4 番目の宝石を順に取り付けることにすると ( 色, 価値 ) が (1, 10),(2, 8),(1, 7),(3, 5) の順に並びます。このとき、価値の合計は 30 です。

入力例 2

5 5
1 10
1 9
1 8
2 7
2 6

出力例 2

-1

条件を満たすように 5 個の宝石を取り付けることはできません。王冠は円形であることに注意をしてください。

入力例 3

12 8
1 10
1 7
1 6
1 1
2 9
2 8
2 3
3 11
3 5
3 4
4 2
5 12

出力例 3

68