Скоро выборы губернатора. Вы работаете на текущего губернатора, поэтому провели несколько опросов, в результате которых для каждого голосующего вы знаете: за кого он будет голосовать на выборах, и сколько нужно ему заплатить, чтобы он проголосовал за текущего губернатора. Какое минимальное количество денег придется потратить, чтобы текущий губернатор победил на выборах? Текущий губернатор победит на выборах, только если он наберет строго больше голосов, чем каждый из остальных кандидатов.
Выходные данные
Выведите единственное целое число — минимальную сумму денег.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
1 2
1 2
2 1
0 0
|
3
|
|
2
|
4
1 2
1 2
2 1
0 0
|
2
|
|
3
|
1
100000 0
|
0
|