Optimal Perket Flavor

Perket is a popular delicacy. To make a perfect Perket, a chef must choose the ingredients carefully to achieve a balanced flavor while retaining its traditional taste. You are given \( n \) ingredients. For each ingredient, you know its acidity \( s \) and bitterness \( b \). When mixing ingredients, the total acidity is the product of the acidities of all chosen ingredients, and the total bitterness is the sum of the bitterness values.

Since a good dish should have a balanced taste, your task is to select at least one ingredient such that the absolute difference between the total acidity and bitterness is minimized. Formally, if you choose a non-empty subset of ingredients, let \( A \) be the product of all \( s \) values and \( B \) be the sum of all \( b \) values, then you need to minimize \( |A - B| \).

inputFormat

The first line contains an integer \( n \) (1 \( \leq n \leq 10 \)), the number of ingredients.

Each of the next \( n \) lines contains two space-separated integers, \( s \) (acidity) and \( b \) (bitterness), representing an ingredient.

outputFormat

Output a single integer, the minimum absolute difference between the total acidity (product of \( s \) values) and total bitterness (sum of \( b \) values) among all non-empty subsets of ingredients.

sample

3
1 7
2 6
3 4

1