T-shirter
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 N T-shirts, which he won in different contests and competitions. Each T-shirt has two characteristics: the importance (a_i) and urgency (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 a_i of the selected T-shirts and the sum of all b_i will as small as possible. You have to find this difference.
Input
The first line contains the number of T-shirts n (1 ≤ n ≤ 25). Each of the following n lines contains two integers: the importance a_i (1 ≤ a_i ≤ 10^15) and the urgency b_i (1 ≤ b_i ≤ 10^15) T-shirts.
Output
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.