Problem : 82 - 二手店

Problem Statistics

Solved Member: 30　　Submission: 94　　User Tried: 31

Statement:

你正為了你家堆積如山的H-game(heuristic game)而煩惱著，正好你最近缺錢，決定到JOI二手店賣掉一些game來籌措金費。

JOI二手店總共把遊戲分為純愛、鬼畜、獵奇等等10個種類，分別用1到10之間的整數來代稱。JOI二手店的價錢計算方法是這樣的，每一款遊戲有他的基準價格。當你同一個種類賣了 T 款遊戲，那麼這一個種類所賣的遊戲當中，每款遊戲的價格會漲價 T-1 元。舉個例子，你在同個種類當中賣了基準價格分別為100円、120円、150円的三款遊戲，那麼真正賣出去的價錢分別為102円、122円、152円。

你身上剛好有 N 款遊戲，你想賣掉 K 款遊戲來籌措金費，你想知道要怎麼賣才能夠使你賣出去的價錢最高。

Task:

給你 N 款遊戲的基準價格以及他的分類，請你計算最多能夠賣多少錢。

Input:Output:

第1行有2個整數，N, K，以空白分隔開來。代表你想賣掉 N 款遊戲的其中 K 款。
接下來 N 行每行有 2 個數字，Ci, Gi，分別代表第 i 款遊戲的價格以及種類。

輸出一個整數，代表你最多可以賣多少錢。

Sample Input:Sample Output:

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

HINT:

2 ≤ N ≤ 2000，代表你擁有幾款遊戲
1 ≤ K < N，代表你想賣幾款遊戲
1 ≤ Ci ≤ 100000 = 10^5，代表第 i 款遊戲的基準價格
1 ≤ Gi ≤ 10，第 i 款遊戲的分類

20%測資滿足： N ≤ 20
20%測資滿足：只有1和2兩種種類的遊戲
10%測資滿足：上面兩條件
30%測資滿足：前兩個條件之一

範例測資當中，選擇第2, 4, 6, 7四款遊戲，種類為2的遊戲各漲價2円。販售價格各為15, 16, 16, 13円，合計60円。

Source:

JOI 2010/2011 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10