Пете подарили n гирь и чашечные весы. Каждая гиря весит ai грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.
Одно перекладывание происходит следующим образом: Петя выбирает некоторую гирю, лежащую на одной чаше весов и перекладывает ее на другую чашу весов. Обратите внимание, что Петя не обязан сделать ровно два перекладывания, он может сделать меньшее количество.
Входные данные
В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа ai, bi (1 ≤ ai ≤ 1000, 1 ≤ bi ≤ 2) — масса гири и номер чаши весов, на которой она находится.
Выходные данные
Требуется вывести одно число — наименьшую разницу весов, которую можно достичь, сделав не более двух перекладываний гирь.
Пример входных и выходных данных
| Ввод |
Вывод |
5
4 2
1 1
8 1
5 2
2 1 |
0 |
6
20 2
3 2
2 1
5 1
1 1
3 2 |
6 |
4
3 2
10 2
8 2
9 2 |
4 |