Description

Perket is a popular dish. To make a good Perket, the chef must choose the ingredients carefully to achieve the most balanced flavor while keeping the traditional taste. You have $n$ available ingredients. For each ingredient, we know its sourness $s$ and bitterness $b$. When we add ingredients, the total sourness is the product of the sourness values of the chosen ingredients; the total bitterness is the sum of the bitterness values of the chosen ingredients.

It is well known that a good dish should be well balanced, so we want to choose a subset of ingredients that minimizes the absolute difference between the total sourness and the total bitterness.

Also, we must add at least one ingredient, because no dish is made with only water.

Description

Input Format

The first line contains an integer $n$, the number of available ingredient types. The next $n$ lines each contain $2$ integers $s_i$ and $b_i$, the sourness and bitterness of the $i$-th ingredient.

Output Format

Output a single integer: the minimum possible absolute difference between the total sourness and the total bitterness.

1
3 10

7

2
3 8
5 8

1

4
1 7
2 6
3 8
4 9

1

Hint

For the third sample, choose the last three ingredients. Then the total sourness is $2 \times 3 \times 4 = 24$, the total bitterness is $6+8+9=23$, and the difference is $1$.

Constraints

• For $100\%$ of the testdata, $1 \leq n \leq 10$, and the total sourness and the total bitterness obtained by using all available ingredients are less than $1 \times 10^9$.

Notes

• This problem is worth $70$ points.
• Translated from COCI2008-2009 CONTEST #2 PERKET, translator
  https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5