T-shirter#4358
Fan Sasha has an unusual surname, and it's associated with the football capital of Italy. Now he's preparing for the regular sports programming meeting. Many famous people will arrive from neighboring countries; therefore, everybody needs to look great. Sasha has T-shirts, which he won in different contests and competitions. Each T-shirt has two characteristics: the importance (a_i) and relevance (b_i). For example, a T-shirt from the world finals 1998, of course, is much more significant than the T-shirt from the country finals 2012. But it looks outdated and irrelevant. During its existence, a 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 be as small as possible. You have to find this difference.
The first line contains the number of T-shirts (1 \le n \le 25). Each of the following lines contains two integers: the importance a_i (1 \le a_i \le 10^{15}) and the relevance b_i (1 \le b_i \le 10^{15}) of the T-shirt.
Output the minimum difference that can be achieved between the sum of all importances of the selected T-shirts and the sum of all relevances. Sasha will take at least one T-shirt.
1-nji mysal