Doyoung's Delicious Food

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.

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.

Print the minimum possible difference between sourness and bitterness.