Футболочник
У фаната Саші доволі незвичне прізвище, воно асоціюється з футбольною столицею Італії. Він збирається на чергові збори зі спортивного програмування. До них злетяться багато відомих осіб з ближнього зарубіжжя, тому, виглядати потрібно гідно. У Саші є 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) футболки.
Вихідні дані
Мінімальну різницю, яку можна отримати між сумою всіх значимостей обраних футболок і сумою всіх актуальностей. Хоча б одну футболку Саша обов'язково візьме, ходити-то в чомусь потрібно.