← 返回题目列表

Codeforces · 1019/A

A. 选举

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

如您所知,暑期信息学学校的大部分学生和老师一年中大部分时间都居住在伯兰。由于腐败现象相当普遍,下面的故事并不少见。

选举即将到来。您知道选民人数和政党数量 - 分别为 $$$n$$$ 和 $$$m$$$。对于每个选民,您都知道他将投票支持哪个政党。然而,只要有一定数额的钱,他就可以轻松改变自己的投票。特别是,如果您给第 $$$i$$$ 位选民 $$$c_i$$$ 字节币,您可以要求他投票给您选择的任何其他政党。

Berland 联合党决定进行一项统计研究 - 您需要计算该党确保其胜利所需花费的最小字节币数量。为了让一个政党赢得选举,它需要获得比任何其他政党严格更多的选票。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3000$$$)——分别是选民人数和政党数量。

以下 $$$n$$$ 行中的每一行都包含两个整数 $$$p_i$$$ 和 $$$c_i$$$ ($$$1 \le p_i \le m$$$, $$$1 \le c_i \le 10^9$$$) - 该选民首选政党的索引以及他重新考虑其决定所需的字节币数量。

Berland 联合党的指数为 $$$1$$$。

输出

打印一个数字——伯兰联合党赢得选举所需的最小字节币数量。

示例

输入 #1

1 2
1 100

输出 #1

0

输入 #2

5 5
2 100
3 200
4 300
5 400
5 900

输出 #2

500

输入 #3

5 5
2 100
3 200
4 300
5 800
5 900

输出 #3

600

注意

在第一个样本中,联合党即使没有购买额外选票也赢得了选举。

在第二个样本中,联合党可以购买第一和第四选民的选票。这样,该党获得两票,而党派 $$$3$$$、$$$4$$$ 和 $$$5$$$ 获得一票,党号 $$$2$$$ 没有投票权。

在第三个样本中,联合党可以购买前三名选民的选票并获胜,获得三票反对第五党的两票。