004 - 古本屋 (Books)

問題

　あなたの町には JOI 古本店という老舗の古本屋があり，あなたは JOI 古本店をよく利用している．それぞれの本には基準価格が定まっており，JOI 古本店に行けばその価格で買い取ってもらえる．
　JOI 古本店では，本を小説・漫画・雑誌など 10 種類のジャンルに分類して扱っている．ジャンルには 1 から 10 までの番号が付けられている．JOI 古本店には，同じジャンルの本をまとめて買い取ってもらうと高値で買い取ってくれるというサービスがある．具体的には，同じジャンルの本をまとめて T 冊買い取ってもらう場合，そのジャンルの本の一冊あたりの買取価格が基準価格より T - 1 円高くなる．例えば，同じジャンルで基準価格 100 円，120 円，150 円の本をまとめて JOI 古本店に売ったとすると，買取価格はそれぞれ 102 円，122 円，152 円となる．
　さて，あなたは一身上の都合で急遽引越しをすることになった．あなたは N 冊の本を持っているが，新しい住居にすべての本を持っていくことは困難なため，N 冊の本のうち K 冊を JOI 古本店に売ることにした．

課題

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

制限

入力

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

• 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 つの条件の少なくとも一方を満たす．

入出力例

入力例 1

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

出力例 1

60

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

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