Horned fan Sasha has unusual surname, and it’s associated with the football capital of Italy. Now he’s preparing for the regular sports programming meeting. A lot of famous persons will fly there from the neighboring countries, therefore, everybody needs to look great. Sasha has \textbf{N} T-shirts, which he won in different contests and competitions. Each T-shirt has two characteristics: the importance (\textbf{a_i}) and urgency (\textbf{b_i}). For example, a T-shirt from the world finals 1998, of course, is much more significant than the T-shirt of the country finals 2012. But it looks outdated and irrelevant. During its existence, the new generation was born. We can argue a lot about which T-shirt is better. Therefore, Sasha decided to take T-shirts so that the difference between the sum of all \textbf{a_i} of the selected T-shirts and the sum of all \textbf{b_i} will as small as possible. You have to find this difference. \InputFile The first line contains the number of T-shirts \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{25}). Each of the following \textbf{n} lines contains two integers: the importance \textbf{a_i} (\textbf{1 }≤ \textbf{a_i} ≤ \textbf{10^15}) and the urgency \textbf{b_i} (\textbf{1 }≤ \textbf{b_i} ≤ \textbf{10^15}) T-shirts. \OutputFile The minimum difference that can be received between the sum of all importances of selected T-shirts, and the sum of all urgencies. Sasha will take at least one T-shirt.