CF1019A.Elections

As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.

Elections are coming. You know the number of voters and the number of parties — $n$ and $m$ respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give $i$-th voter $c_i$ bytecoins you can ask him to vote for any other party you choose.

The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.

众所周知，暑期信息学学校（Summer Informatics School）的大部分学生和教师一年中多数时间都居住在贝尔兰德（Berland）。由于该国腐败现象十分普遍，下面这种情形并不少见。

选举即将来临。已知选民总数与政党总数分别为 $n$ 和 $m$。对于每位选民，你都知道他原本打算投票给哪个政党。然而，只要支付一定金额的钱，他便很容易改变自己的投票意向。具体而言，若向第 $i$ 位选民支付 $c_i$ 字节币（bytecoins），你便可要求他改投任意你指定的其他政党。

贝尔兰德联合党（The United Party of Berland）决定开展一项统计研究——你需要计算该党为确保胜选所需花费的最小字节币数量。一个政党要赢得选举，其得票数必须严格多于其他任何一个政党的得票数。

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 3000$) — the number of voters and the number of parties respectively.

Each of the following $n$ lines contains two integers $p_i$ and $c_i$ ($1 \le p_i \le m$, $1 \le c_i \le 10^9$) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.

The United Party of Berland has the index $1$.

输入的第一行包含两个整数 $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$），分别表示该选民所偏好的政党编号以及使其改变决定所需的字节币数量。

贝尔兰联合党（United Party of Berland）的编号为 $1$。

Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.

输出一个整数——即伯兰联合党赢得选举所需的最少字节币数量。

In the first sample, The United Party wins the elections even without buying extra votes.

In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties $3$, $4$ and $5$ get one vote and party number $2$ gets no votes.

In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.

在第一个样例中，联合党即使不额外购买选票也能赢得选举。

在第二个样例中，联合党可以购买第一位和第四位选民的选票。这样，该党获得两票，而第 3、4、5 号政党各获得一票，第 2 号政党则一票未得。

在第三个样例中，联合党可以购买前三位选民的选票并获胜，以三票对第五政党的两票取胜。