Футболочник
У фаната Саши довольно необычная фамилия, ассоциирующаяся с футбольной столицей Италии. Он собирается на очередные сборы, посвещённые спортивному программированию. На них слетятся многие известные личности из ближнего зарубежья, поэтому, выглядеть нужно достойно. У Саши есть N футболок, выигранных в различных турнирах и соревнованиях. Каждая футболка имеет две характеристики: значимость (a_i) и актуальность (b_i). Например, футболка с финала мира 1998-ого года, конечно, гораздо значимее, чем футболка с финала страны 2012-ого года. Но она изрядно устарела и выглядит неактуальной. За время её существования целое поколение сменилось.
Можно долго спорить о том, какая футболка лучше. Поэтому, Саша решил набрать футболки так, чтобы разница между суммой всех a_i у выбранных футболок и суммой всех b_i была как можно меньше. Эту разницу Вам и предстоит найти.
Входные данные
В первой строке задаётся количество футболок n (1 ≤ n ≤ 25). Каждая из следующих n строк содержит по два целых числа: значимость a_i (1 ≤ a_i ≤ 10^15) и актуальность b_i (1 ≤ b_i ≤ 10^15) футболки.
Выходные данные
Минимальную разницу, которую можно получить между суммой всех значимостей выбранных футболок и суммой всех актуальностей. Хотя бы одну футболку Саша обязательно возьмёт, ходить-то в чём-то нужно.