古本屋(Books)

あなたの町にはJOI 古本店という老舗の古本屋があり，あなたはJOI 古本店をよく利用している．それぞれの本には基準価格が定まっており，JOI 古本店に行けばその価格で買い取ってもらえる．

JOI 古本店では，本を小説,漫画,雑誌など10 種類のジャンルに分類して扱っている．ジャンルには1から10 までの番号が付けられている．JOI 古本店には，同じジャンルの本をまとめて買い取ってもらうと高値で買い取ってくれるというサービスがある．具体的には，同じジャンルの本をまとめてT 冊買い取ってもらう場合，そのジャンルの本の一冊あたりの買取価格が基準価格よりT - 1 円高くなる．例えば，同じジャンルで基準価格100 円，120 円，150 円の本をまとめてJOI 古本店に売ったとすると，買取価格はそれぞれ102 円，122 円，152 円となる．

さて，あなたは一身上の都合で急遽引越しをすることになった．あなたはN 冊の本を持っているが，新しい住居にすべての本を持っていくことは困難なため，N 冊の本のうちK 冊をJOI 古本店に売ることにした．

課題

N 冊の本それぞれの基準価格とジャンルの番号が与えられるとき，合計買取価格の最大値を求めるプログラムを作成せよ．

制限

2 ≤ N ≤ 2000    あなたが持っている本の冊数
1 ≤ K < N    JOI 古本店に売る本の冊数
1 ≤ C_i ≤ 100000 = 10⁵    i 番目の本の基準価格
1 ≤ G_i ≤ 10    i 番目の本のジャンルの番号

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数N, K が空白を区切りとして書かれており，あなたの持っている本の冊数がN で，そのうちK 冊をJOI 古本店に売ることを表す．
• 続くN 行にはあなたの持っている本の情報が書かれている．i + 1 行目(1 ≤ i ≤ N) には，整数C_i,G_iが空白を区切りとして書かれており，i 番目の本の基準価格がC_i で，ジャンルの番号がG_i であることを表す．

出力

標準出力に，合計買取価格の最大値を表す整数を1 行で出力せよ．

採点基準

採点用データのうち，
配点の20% 分については，N ≤ 20 を満たす．
配点の20% 分については，すべての本のジャンルは1 または2 である．
配点の10% 分については，これら2 つの条件の両方を満たす．
配点の30% 分については，これら2 つの条件の少なくとも一方を満たす．

入出力の例

入力例

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2

出力例

60

この入力例では，2 番目，4 番目，6 番目，7 番目の4 冊の本を売ったとき，ジャンル2 の本の買取価格が1 冊あたり2 円高くなるので，これらの本の買取価格は以下のようになる．

2
4
6
7

13
14
16
11

2
2
3
2

15
16
16
13

よって合計買取価格は15 + 16 + 16 + 13 = 60 円である．このとき合計買取価格は最大となる．