Doyoung's Delicious Food

Time limit1sMemory limit128 MB

Summary

Given up to 10 ingredients with sourness and bitterness, choose a non-empty subset minimizing the absolute difference between the product of sourness and sum of bitterness, using brute force over all subsets.

Level: Easy3 of 10
Topics: Brute force, Math
Solved: No attempts yet

Problem

Doyoung once became famous as a creative noodle cook. Now he wants to try making a new dish that he has never made before.

There are N ingredients in front of Doyoung. For each ingredient, he knows its sourness S and bitterness B. When several ingredients are used in one dish, the dish's sourness is the product of the sourness values of the chosen ingredients, and its bitterness is the sum of their bitterness values.

Few people enjoy food that is too sour or too bitter. Doyoung wants to choose ingredients so that the difference between the dish's sourness and bitterness is as small as possible. At least one ingredient must be used.

Input

The first line contains the number of ingredients N (1 <= N <= 10).

Each of the next N lines contains two integers S and B, the sourness and bitterness of one ingredient.

If all ingredients are used, both the sourness and bitterness of the resulting dish are positive integers less than 1,000,000,000.

Output

Print the minimum possible difference between sourness and bitterness.

Examples3

Example 1
Input
```
1
3 10
```
Expected output
```
7
```
Example 2
Input
```
2
3 8
5 8
```
Expected output
```
1
```
Example 3
Input
```
4
1 7
2 6
3 8
4 9
```
Expected output
```
1
```