레이팅 미적용설명
"Perket"은 널리 알려진 맛있는 요리이다. Perket이 제대로 되려면, 요리사는 전통을 지키면서도 가장 풍부한 맛을 내도록 재료를 신중하게 골라야 한다.
여러분에게는 \(N\)가지 재료가 있다. 각 재료에 대해 신맛 \(S\)와 쓴맛 \(B\)를 알고 있다. 여러 재료를 사용할 때 전체 신맛은 모든 재료의 신맛의 곱이고, 전체 쓴맛은 모든 재료의 쓴맛의 합이다.
모두가 알다시피 perket은 시지도 쓰지도 않아야 한다. 즉, 신맛과 쓴맛의 차의 절댓값이 최소가 되도록 재료를 골라야 한다.
또한 재료를 적어도 하나는 사용해야 한다. 메인 요리로 물을 내놓을 수는 없으니까.
제약
입력 형식
첫째 줄에 사용할 수 있는 재료의 수인 정수 \(N\) (\(1 \le N \le 10\))이 주어진다.
다음 \(N\)개의 줄에는 공백으로 구분된 두 정수, 각 재료의 신맛과 쓴맛이 주어진다.
입력 데이터는 모든 재료로 요리를 만들었을 때 신맛과 쓴맛이 모두 \(1\,000\,000\,000\)보다 작도록 주어진다.
출력 형식
신맛과 쓴맛의 차이의 최솟값을 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
예제 1
입력
1
3 10출력
7예제 2
입력
2
3 8
5 8출력
1예제 3
입력
4
1 7
2 6
3 8
4 9출력
1설명
We choose the last three ingredients. The total sourness is 234=24 and bitterness is 6+8+9=23. The difference is 1.
문제 정보
태그