Футболочник#4358
У фаната Саші доволі незвичне прізвище, воно асоціюється з футбольною столицею Італії. Він збирається на чергові збори зі спортивного програмування. До них злетяться багато відомих осіб із сусідніх країн, тому виглядати потрібно гідно. У Саші є футболок, виграних у різних турнірах та змаганнях. Кожна футболка має дві характеристики: значимість (a_i) та актуальність (b_i). Наприклад, футболка з фіналу світу року, звичайно, набагато більш значуща, ніж футболка з фіналу країни . Але вона неабияк застаріла і виглядає неактуальною. За час її існування ціле покоління змінилося.
Можна довго сперечатися про те, яка футболка краща. Тому Сашко вирішив обрати футболки так, щоб різниця між сумою всіх a_i у обраних футболок і сумою всіх b_i була якомога меншою. Цю різницю вам і потрібно знайти.
У першому рядку задається кількість футболок (1 \le n \le 25). Кожен з наступних рядків містить по два цілих числа: значимість a_i (1 \le a_i \le 10^{15}) і актуальність b_i (1 \le b_i \le 10^{15}) футболки.
Виведіть мінімальну різницю, яку можна отримати між сумою всіх значимостей вибраних футболок і сумою всіх актуальностей. Хоча б одну футболку Саша обов'язково візьме, бо ходити-то в чомусь потрібно.
Приклад 1