题目描述

你打算在俄罗斯的一个小城市竞选州长，你对投票人的投票意向进行了调查。现在，对于城市中每一个参与投票的人，你都知道他们会投谁的票，也知道贿赂那个人投票给你需要花多少钱（我从未见过有如此厚颜无耻之人）。

为了赢得选举，你的得票数必须比其他参与竞选的人多。那么你至少要破费多少钱才能赢得竞选呢？

输入格式

第一行：参与投票的人数 $n$，$1\le n\le 10^5$。

接下来 $n$ 行，每行两个数 $a_i,b_i$，$0\le a_i\le 10^5$，$0\le b_i\le 10^4$。其中 $a_i$ 表示这位投票人想投给的竞选者编号（你自己的编号为 $0$）；$b_i$ 表示贿赂他投票给你需要的金额。

输出格式

输出一个整数表示答案。

5
1 2
1 2
1 2
2 1
0 0

3

4
1 2
1 2
2 1
0 0

2

1
100000 0

0