B. Шаасс и книжная полка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Шаасса есть n книг. Он хочет смастерить полку подо все свои книги. Также он хочет, чтобы размеры полки были как можно меньше. Толщина i-ой книги равна ti, а ширина ее страниц равна wi. Толщина каждой книги — либо 1, либо 2. Высота страниц всех книг одинаковая.

Шаасс кладет книги на полку следующим образом. Сперва он выбирает несколько книг и кладет их вертикально. Затем он кладет оставшиеся книги горизонтально над вертикальными книгами. Сумма ширин горизонтальных книг не должна превышать суммарную толщину вертикальных книг. На рисунке ниже приведен пример, как можно уложить книги.

Помогите Шаассу вычислить минимальную достижимую общую толщину вертикальных книг, если он хочет уложить все книги на полку описанным способом.

Входные данные

В первой строке входных данных записано целое число n, (1 ≤ n ≤ 100). В каждой из следующих n строк записано два целых числа ti и wi, обозначающие толщину и ширину i-ой книги соответственно (1 ≤ ti ≤ 2, 1 ≤ wi ≤ 100).

Выходные данные

В единственной строке выведите минимальную достижимую общую толщину вертикальных книг.

Примеры
Входные данные
5
1 12
1 3
2 15
2 5
2 1
Выходные данные
5
Входные данные
3
1 10
2 1
2 4
Выходные данные
3