Problem Statement

Mom has two precious children, A and B. Mom loves them both equally and raises them without favoring either one. Mom now has n items, and she intends to distribute all n items between the two children. However, the two children get different levels of satisfaction when they receive an item. For example, if A receives a sweet bean bun, A's satisfaction is 15, and if B receives it, B's satisfaction is 30. Since Mom loves them both, she has decided to distribute the items so that the difference between A's total satisfaction and B's total satisfaction is minimized. Write a program that, from the data, finds the minimum difference (that is, the absolute value of the difference). The data is as follows.

The number of items n.
The following n lines give the two children's satisfaction values Ai and Bi for the items.
A1 is the satisfaction when A receives item 1. B1 is the satisfaction when B receives item 1.
In general, Ai is the satisfaction when A receives item i, and Bi is the satisfaction when B receives item i.

Input

$n$
$A_1$ $B_1$
$A_2$ $B_2$
$\dots$
$A_{n}$ $B_{n}$

$1 \leq n \leq 32$
$0 \leq Ai \leq5000000000$
$0 \leq Bi \leq5000000000$
Ai is A's satisfaction when A receives item i, and Bi is B's satisfaction when B receives item i. For both children, the satisfaction values of the items received are simply summed. Compute the difference in total satisfaction when the items are distributed so that the difference in satisfaction is minimized.

Output

Output the minimum absolute value of the difference in satisfaction between the two children.

Sample

1
10 15

10

3
25 14
25 23
32 10

1