문제
"퍼킷"은 널리 알려진 맛있는 음식이다.
퍼킷이 맛있는 음식으로 전통을 유지할 수 있던 이유는 요리사들이 "퍼킷"의 맛을 위해 재료를 고르는데 있어 신중했기 때문이다.
여러분에게 N개의 재료가 주어진다. S는 신맛을 B는 쓴맛을 뜻한다고 하자.
다양한 재료가 쓰인다고 할 때, 신맛의 합은 우리가 선택한 각 신맛 재료의 신맛 지수들을 곱한 값이고
쓴맛의 합은 우리가 선택한 각 쓴맛재료의 쓴맛 지수들을 더한 값이다.
그런데 "퍼킷"은 신맛도 쓴맛도 나지 않는다. 따라서 우리는 신맛의 곱과 쓴맛의 합의 차가 최소가 되도록 하고자 한다.
그러나 적어도 하나 이상의 재료를 선택해야 한다. 그리고 물을 사용할 수 없다.
입력
요리에 사용될 재료의 수 N(1≤N≤10)이 들어온다. 그리고 N개의 줄에는 각 재료의 S와 B가 주어진다.
각 재료의 신맛과 쓴맛은 양의 정수이며,
모든 재료의 신맛의 곱과 쓴맛의 합은 모두 1,000,000,000을 넘지 않는다.
출력
신맛의 곱과 쓴맛의 합 사이의 가능한 가장 작은 차를 출력하시오.
예제1
입력
1
3 10
출력
7
예제2
입력
2
3 8
5 8
출력
1
예제3
입력
4
1 7
2 6
3 8
4 9
출력
1
우리는 세 개의 재료를 선택할 수 있다. 신맛의 곱은 2×3×4=24이고 쓴맛의 합은 6+8+9=23이 되며 그 차는 1이다.
출처
COCI 2008/2009 contest2 3