퍼켓은 매우 유명하고 맛있는 식사다. 제대로 된 맛을 얻기 위해서는 재료를 잘 선택해야 한다.

당신은 N 가지의 재료를 가지고 있다. 각 재료의 신맛을 S , 썬맛을 B 라고 하자. 여러가지 재료를 사용할 때 , 전체의 신 맛은 각 재료의 썬맛의 곱이고 전체의 썬 맛은 각 재료의 합이다.

모두가 알 듯이 , 퍼켓은 시어시도 써서도 안된다. 신맛과 썬맛의 차이를 가장 최소로 할 수 있는 재료를 선택하길 원한다.

적어도 한가지 이상의 재료를 선택해야 하고 물을 탈 수는 없다.

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.

입력

• The 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.

출력

입출력 예

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 

EXAMPLES

출처: coci 2008/2009 3/6