Codah ClubGyakorolj. Küldd be. Fejlődj.
Bejelentkezés
Magyar
#00018C

Perket

"Perket" is a widely known and delicious meal. For perket to be what it ,cooks must carefully choose the ingredients to get the fullest taste possible while keeping the meal traditional.

You have N ingredients at your disposal. For each we know its sourness S and bitterness B. When using multiple ingredients, the total sourness is the product of sourness amounts of all ingredients, while the total bitterness is the sum of bitterness amounts of all ingredients.

As everyone knows, perket is supposed to be neither sour nor bitter; we want to choose the ingredients so that the absolute difference between sourness and bitterness is the smallest.

Also, it is necessary to use at least one ingredient; you can't serve water as the main course.


InputThe first line contains the integer N (1 ≤ N ≤ 10), the number of ingredients at our disposal.
Each of the next N lines contains two integers separated by a space, the sourness and bitterness of each ingredient.
The input data will be such that, if we make a meal with all ingredients, both the sourness and bitterness will be less than 1 000 000 000.

OutputOutput the smallest possible difference between sourness and bitterness.

Input:
1
3 10
Output:
7

Input:
2
3 8
5 8
Output:
1

Input:
4
1 7
2 6
3 8
4 9
Output:
1

In the third example, we choose the last three ingredients. The total sourness is then 2·3·4=24 and bitterness is 6+8+9=23. The difference is 1.


Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.