Məsələlər
Футболочник
Футболочник
У фаната Саши довольно необычная фамилия, ассоциирующаяся с футбольной столицей Италии. Он собирается на очередные сборы, посвещённые спортивному программированию. На них слетятся многие известные личности из ближнего зарубежья, поэтому, выглядеть нужно достойно. У Саши есть \textbf{N }футболок, выигранных в различных турнирах и соревнованиях. Каждая футболка имеет две характеристики: значимость (\textbf{a_i}) и актуальность (\textbf{b_i}). Например, футболка с финала мира 1998-ого года, конечно, гораздо значимее, чем футболка с финала страны 2012-ого года. Но она изрядно устарела и выглядит неактуальной. За время её существования целое поколение сменилось.
Можно долго спорить о том, какая футболка лучше. Поэтому, Саша решил набрать футболки так, чтобы разница между суммой всех \textbf{a_i} у выбранных футболок и суммой всех \textbf{b_i} была как можно меньше. Эту разницу Вам и предстоит найти.
\InputFile
В первой строке задаётся количество футболок \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{25}). Каждая из следующих \textbf{n} строк содержит по два целых числа: значимость \textbf{a_i} (\textbf{1 }≤ \textbf{a_i} ≤ \textbf{10^15}) и актуальность \textbf{b_i} (\textbf{1 }≤ \textbf{b_i} ≤ \textbf{10^15}) футболки.
\OutputFile
Минимальную разницу, которую можно получить между суммой всех значимостей выбранных футболок и суммой всех актуальностей. Хотя бы одну футболку Саша обязательно возьмёт, ходить-то в чём-то нужно.
Giriş verilənləri #1
3 100 9 10 90 5 16
Çıxış verilənləri #1
0