### Indian National Olympiad in Informatics

### Online Programming Contest, 25-26 March 2006

### Advanced Division

Problem 1: Equal Gifts, *(R Shreevatsa, CMI)*

It is Lavanya's birthday and several families have been invited
for the birthday party. As is customary, all of them have brought
gifts for Lavanya as well as her brother Nikhil. Since their friends
are all of the erudite kind, everyone has brought a pair of books.
Unfortunately, the gift givers did not clearly indicate which book in
the pair is for Lavanya and which one is for Nikhil. Now it is up to
their father to divide up these books between them.

He has decided that from each of these pairs, one book will go to
Lavanya and one to Nikhil. Moreover, since Nikhil is quite a keen
observer of the value of gifts, the books have to be divided in such a
manner that the total value of the books for Lavanya is as close as
possible to total value of the books for Nikhil. Since Lavanya and
Nikhil are kids, no book that has been gifted will have a value
higher than 300 Rupees.

Suppose there are 4 pairs of books whose cost in Rupees are:

(3,5), (7,11), (8,8), (2,9)

By giving the books worth 3,7,8 and 2 to Lavanya and the rest to
Nikhil, the net difference in value would be 5+11+8+9-3-7-8-2 = 13.
However, by giving books worth 3,7,8 and 9 to Lavanya and the rest to
Nikhil, their father can ensure that the difference in values is just
1. You can verify that you cannot do better than this.

You task is to help their father decide how to divide the
books.

Input format

The first line of the input contains a single integer *N*
indicating the number of pairs of books that need to be divided
between Lavanya and Nikhil. The next *N* lines, lines
2,3,…,*N*+1, each contain two integers indicating the costs of
one pair of books.

Output format

A single integer indicating the smallest possible difference
between the total value of books assigned to Lavanya and Nikhil.

Test Data:

You may assume that *N* ≤ 150 and that the cost of every
book is in the range 1…300.

Example:

Here is the sample input and output corresponding to the example
discussed above.

Sample Input

4
3 5
7 11
8 8
2 9

Sample Output

1