配点: 100 点
你的城市有一家名为 JOI 古书店的老店,你经常光顾 JOI 古书店。每本书都有固定价格,在 JOI 古书店可以按该价格回收。
JOI二手书店出售小说、漫画、杂志等书籍。 10 它分为不同的流派。在流派中 它们的编号最大为 1 从 10 。 JOI二手书店有一项服务,如果批量购买同类型的书籍,可以以高价购买。具体来说,相同类型的书籍被分组在一起。 T 购买书籍时,该类型的每本书的购买价格低于标准价格。 T − 1 日元将会升值。例如,同一类型的标准价格 100 円,120 円,150 如果你把一堆日元书卖给JOI二手书店,每本的购买价格是 102 円,122 円,152 变成日元。
现在,您因个人情况决定突然搬家。你是 N 我有很多书,但很难把它们全部带到我的新住所,所以N 书籍 K 我决定把这本书卖给JOI二手书店。
課題
N 给定每本书的标准价格和类型编号,编写一个程序来查找最大总购买价格。
制限
| 2 \leqq N \leqq 2\,000 | 您拥有的图书数量 |
| 1 \leqq K < N | JOI 出售给二手书店的书籍数量 |
| 1 \leqq C_i \leqq 100\,000\,(=10^5) | i 本书的基本价格 |
| 1 \leqq G_i \leqq 10 | i 第本书类型编号 |
入力
从标准输入读取以下输入。
- 1 行是一个整数 N, K 以空格作为分隔符,您拥有的书籍数量为 N 所以,最终 K 表示向 JOI 旧书店出售一本书。
- 继续 N 行包含有关您拥有的图书的信息。i + 1 行目 (1\leqq i\leqq N) 是一个整数 C_i,G_i 以空格作为分隔符写入, 第i 本书的基本价格是 C_i ,流派编号为 G_i 。
出力
表示总购买价格最大值的整数被发送到标准输出。 输出为 1 行。
採点基準
评分数据中,
积分分配 20 对于%,N\leqq 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 由于日元升值,这些书籍的购买价格如下。
| 番号 | 基準価格 | 类型 | 買取価格 |
|---|---|---|---|
| 2 | 13 | 2 | 15 |
| 4 | 14 | 2 | 16 |
| 6 | 16 | 3 | 16 |
| 7 | 11 | 2 | 13 |
因此,总购买价格为 15 + 16 + 16 + 13 = 60 这是一个圆圈。此时,购买总价最大。