← 返回题目列表

AtCoder · joi2011ho2

B. 二手书店(书籍)

中文机器翻译题面 查看原题

配点: 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 这是一个圆圈。此时,购买总价最大。