У Шаасса есть n книг. Он хочет смастерить полку подо все свои книги. Также он хочет, чтобы размеры полки были как можно меньше. Толщина i-ой книги равна ti, а ширина ее страниц равна wi. Толщина каждой книги — либо 1, либо 2. Высота страниц всех книг одинаковая.
Шаасс кладет книги на полку следующим образом. Сперва он выбирает несколько книг и кладет их вертикально. Затем он кладет оставшиеся книги горизонтально над вертикальными книгами. Сумма ширин горизонтальных книг не должна превышать суммарную толщину вертикальных книг. На рисунке ниже приведен пример, как можно уложить книги.
Помогите Шаассу вычислить минимальную достижимую общую толщину вертикальных книг, если он хочет уложить все книги на полку описанным способом.
Выходные данные
В единственной строке выведите минимальную достижимую общую толщину вертикальных книг.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 12
1 3
2 15
2 5
2 1
|
5
|
|
2
|
3
1 10
2 1
2 4
|
3
|