MemSQL Start[c]UP 2.0 - Round 2 |
---|
Закончено |
Скоро выборы губернатора. Вы работаете на текущего губернатора, поэтому провели несколько опросов, в результате которых для каждого голосующего вы знаете: за кого он будет голосовать на выборах, и сколько нужно ему заплатить, чтобы он проголосовал за текущего губернатора. Какое минимальное количество денег придется потратить, чтобы текущий губернатор победил на выборах? Текущий губернатор победит на выборах, только если он наберет строго больше голосов, чем каждый из остальных кандидатов.
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество голосующих в городе. В каждой из следующих n строк записано два целых числа ai и bi (0 ≤ ai ≤ 105; 0 ≤ bi ≤ 104), где ai обозначает номер кандидата, за которого будет голосовать i-й человек, а bi обозначает количество денег, которое требуется, чтобы подкупить его. Текущий губернатор имеет номер 0, поэтому, если ai = 0 (человек голосует за текущего губернатора), то и bi также равно 0.
Выведите единственное целое число — минимальную сумму денег.
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
Название |
---|