您正在竞选俄罗斯一座小城市的州长。你进行了一些民意调查并做了一些研究,对于这个城市中的每个人,你都知道他会投票给谁,以及贿赂那个人让他投票给你而不是他现在想投票给谁需要多少钱。你很好奇,你最少需要花多少钱行贿才能赢得选举。要赢得选举,您需要比任何其他候选人拥有更多的选票。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 该城市的选民人数。接下来的 n 行中的每一行都描述一个选民,并包含两个整数 ai 和 bi (0 ≤ ai ≤ 105; 0 ≤ bi ≤ 104) — 选民要投票的候选人的编号以及您需要支付给他才能改变主意的金额。你是候选人0(所以如果有选民想投票给你,ai就等于0,在这种情况下bi也将等于0)。
输出
打印一个整数 - 赢得选举所需花费的最小金额。
示例
输入 #1
5 1 2 1 2 1 2 2 1 0 0
输出 #1
3
输入 #2
4 1 2 1 2 2 1 0 0
输出 #2
2
输入 #3
1 100000 0
输出 #3
0