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.
## Input
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$.
## Output
Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.
[samples]
## Note
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.
正如你所知，夏季信息学学校的大多数学生和教师一年中的大部分时间都住在贝兰。由于那里腐败现象相当普遍，以下故事并不罕见。
选举即将来临。你知道选民人数和政党数量 —— 分别为 $n$ 和 $m$。对于每个选民，你知道他将投票给哪个政党。然而，只要支付一定数量的钱，他就可以轻易改变自己的投票。具体来说，如果你给第 $i$ 个选民 $c_i$ 字节币，你就可以要求他投票给你指定的任何其他政党。
贝兰联合党决定进行一项统计研究 —— 你需要计算该党赢得选举所需的最少字节币数量。为了赢得选举，一个政党必须获得比任何其他政党都更多的票数。
输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 3000$) —— 分别表示选民人数和政党数量。
接下来的 $n$ 行中，每行包含两个整数 $p_i$ 和 $c_i$ ($1 lt.eq p_i lt.eq m$, $1 lt.eq c_i lt.eq 10^9$) —— 表示该选民原本支持的政党编号以及让他改变决定所需的字节币数量。
贝兰联合党的编号为 $1$。
请输出一个数字 —— 贝兰联合党赢得选举所需的最少字节币数量。
在第一个样例中，贝兰联合党即使不购买额外选票也能赢得选举。
在第二个样例中，贝兰联合党可以购买第一个和第四个选民的投票。这样该党获得两票，而政党 $3$、$4$ 和 $5$ 各获得一票，政党 $2$ 获得零票。
在第三个样例中，贝兰联合党可以购买前三个选民的投票，从而以三票对第五政党两票获胜。
## Input
输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 3000$) —— 分别表示选民人数和政党数量。接下来的 $n$ 行中，每行包含两个整数 $p_i$ 和 $c_i$ ($1 lt.eq p_i lt.eq m$, $1 lt.eq c_i lt.eq 10^9$) —— 表示该选民原本支持的政党编号以及让他改变决定所需的字节币数量。贝兰联合党的编号为 $1$。
## Output
请输出一个数字 —— 贝兰联合党赢得选举所需的最少字节币数量。
[samples]
## Note
在第一个样例中，贝兰联合党即使不购买额外选票也能赢得选举。
在第二个样例中，贝兰联合党可以购买第一个和第四个选民的投票。这样该党获得两票，而政党 $3$、$4$ 和 $5$ 各获得一票，政党 $2$ 获得零票。
在第三个样例中，贝兰联合党可以购买前三个选民的投票，从而以三票对第五政党两票获胜。
**Definitions**
Let $ n, m \in \mathbb{Z} $ be the number of voters and parties, respectively.
Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence where $ p_i \in \{1, 2, \dots, m\} $ denotes the initial party preference of voter $ i $.
Let $ C = (c_1, c_2, \dots, c_n) $ be a sequence where $ c_i \in \mathbb{Z}^+ $ denotes the cost to sway voter $ i $ to vote for any other party.
Let $ U = 1 $ denote the index of the United Party of Berland.
Define $ V_j = |\{ i \in \{1, \dots, n\} \mid p_i = j \}| $ as the initial number of votes for party $ j $.
Let $ S \subseteq \{1, \dots, n\} $ be a subset of voters to be swayed. For each voter $ i \in S $, we may assign their vote to any party $ j \ne p_i $, at cost $ c_i $.
**Constraints**
1. $ 1 \le n, m \le 3000 $
2. $ 1 \le p_i \le m $, $ 1 \le c_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. The United Party (party 1) may only receive votes from voters originally not voting for it, or retain its own votes.
**Objective**
Find the minimum total cost to assign votes such that:
$$
V_1' > \max_{j \in \{2, \dots, m\}} V_j'
$$
where $ V_j' $ is the final number of votes for party $ j $, obtained by:
- $ V_1' = V_1 + x $, where $ x $ is the number of voters swayed to vote for party 1,
- $ V_j' = V_j - y_j + z_j $ for $ j \ge 2 $, where $ y_j $ is the number of voters originally voting for $ j $ who are swayed away, and $ z_j $ is the number of voters swayed *to* party $ j $ from other parties (including party 1),
- $ \sum_{j=2}^m y_j = \sum_{j=2}^m z_j = x $, and $ z_1 = 0 $,
- The total cost is the sum of $ c_i $ over all swayed voters $ i $.
Equivalently, we seek the minimum cost to redistribute votes such that party 1 has strictly more votes than every other party.