30896번 - 두 팀으로 나누기

문제

$N$명의 사람들이 모여서 경기를 하려고 한다. 각 사람은 팀워크 점수 $A_i$ 와, 실력 점수 $B_i$를 가지고 있다. 점수는 모두 정수이다.

사람들을 적절히 두 팀으로 나누려고 한다. 이때, 팀 $S$의 능력은 다음과 같이 정의된다.

$$\min_{i\in S}(A_i) \times \sum_{i\in S}{B_i}$$

즉, 팀원 중 가장 낮은 팀워크 점수와 모든 팀원의 실력 점수 합을 곱한 것이 팀의 능력이 된다.

고민하던 사람들은 세계적인 감독 광재에게 물어보기로 했다. 광재는 명성에 걸맞게 최적의 방법을 찾으려 한다. 광재를 도와 두 팀의 능력 차이가 최소가 되는 방법을 찾아보자.

두 팀의 구성원의 수가 같을 필요는 없고, 각 팀에는 한 명 이상의 선수가 포함되어야 한다.

입력

첫 번째 줄에 사람의 수 $N$이 주어진다. $(2 ≤ N ≤ 1000)$

두 번째 줄부터 $N$줄 동안 각각의 팀워크 점수 $A_i$ 와, 실력 점수 $B_i$ 가 주어진다. $(1 ≤ A_i, B_i ≤ 100)$

출력

두 팀의 능력 차이가 최소가 되게 나눴을 때 능력 차이를 출력한다.

제한

힌트