eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Футболочник

Футболочник

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

У фаната Саши довольно необычная фамилия, ассоциирующаяся с футбольной столицей Италии. Он собирается на очередные сборы, посвещённые спортивному программированию. На них слетятся многие известные личности из ближнего зарубежья, поэтому, выглядеть нужно достойно. У Саши есть N футболок, выигранных в различных турнирах и соревнованиях. Каждая футболка имеет две характеристики: значимость (a_i) и актуальность (b_i). Например, футболка с финала мира 1998-ого года, конечно, гораздо значимее, чем футболка с финала страны 2012-ого года. Но она изрядно устарела и выглядит неактуальной. За время её существования целое поколение сменилось.

Можно долго спорить о том, какая футболка лучше. Поэтому, Саша решил набрать футболки так, чтобы разница между суммой всех a_i у выбранных футболок и суммой всех b_i была как можно меньше. Эту разницу Вам и предстоит найти.

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

В первой строке задаётся количество футболок n (1 n25). Каждая из следующих n строк содержит по два целых числа: значимость a_i (1 a_i10^15) и актуальность b_i (1 b_i10^15) футболки.

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

Минимальную разницу, которую можно получить между суммой всех значимостей выбранных футболок и суммой всех актуальностей. Хотя бы одну футболку Саша обязательно возьмёт, ходить-то в чём-то нужно.

Пример

Входные данные #1
3
100 9
10 90
5 16
Выходные данные #1
0
Автор Борис Соколов
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года