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