Problem Description

Perket is a popular dish. To make Perket, a chef must carefully choose ingredients to maintain traditional flavors while achieving the most comprehensive taste. You have $n$ types of available ingredients. For each ingredient, we know its acidity $s$ and bitterness $b$. When adding ingredients, the total acidity is the product of the acidity of each ingredient; the total bitterness is the sum of the bitterness of each ingredient.

It is well-known that a dish should have a balanced taste, so we want to select ingredients such that the absolute difference between the total acidity and total bitterness is minimized.

Additionally, we must add at least one ingredient, as no dish is made with just water.

Input Format

The first line contains an integer $n$, representing the number of available ingredient types.

The next $n$ lines each contain two integers $s_i$ and $b_i$, representing the acidity and bitterness of the $i$-th ingredient.

Output Format

A single line containing an integer, representing the minimum absolute difference between the total acidity and total bitterness.

Sample Input and Output

Input Sample #1

1
3 10

Output Sample #1

7

Input Sample #2

2
3 8
5 8

Output Sample #2

1

Input Sample #3

4
1 7
2 6
3 8
4 9

Output Sample #3

1

Notes

Data Size and Constraints

For $100\%$ of the data, $1 \leq n \leq 10$, and the total acidity and total bitterness when using all available ingredients are less than $1 \times 10^9$, with acidity and bitterness not both being $1$ and $0$.

Notes

• This problem is worth $70$ points.
• The problem is translated from COCI2008-2009 CONTEST #2 PERKET, translated by @mnesia.

见题面 Input 部分

见题面 Output 部分