선거

오늘 선거가 열렸다. 번호 $1$부터 $n$까지의 정당 $n$개가 이 선거에 참여했고, 각 정당이 얻은 득표수에 따라 $m$개의 의석이 정당에 배분되었다. 의석 배분에는 다음 알고리즘이 사용되었다.

정당 $1, 2, \ldots, n$이 각각 $c_1, c_2, \ldots, c_n$표를 얻었다고 하자. $s = c_1 + c_2 + \ldots + c_n$이라 두자. 먼저 각 $i$에 대해 정당 $i$에 $\lfloor \frac{c_i}{s} \cdot m \rfloor$개의 의석을 배분한다. 그런 다음 남은 의석을 $\frac{c_i}{s} \cdot m$의 소수 부분이 큰 정당부터 한 정당에 하나씩 배분한다. 동점인 경우 번호가 작은 정당이 우선한다.

다음 정보를 알고 있다.

• 정당 $1, 2, \ldots, n$은 각각 정확히 $a_1, a_2, \ldots, a_n$표를 얻었다.
• 정당 $1, 2, \ldots, n$은 각각 적어도 $b_1, b_2, \ldots, b_n$개의 의석을 얻었다.

총 의석수 $m$의 가능한 최솟값을 구하시오.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 100$). 다음 $n$개의 줄에 각각 정수 한 쌍 $a_i$와 $b_i$가 주어진다 ($1 \le a_i \le 1000$, $0 \le b_i \le 10^9$). $b_i \ge 1$인 $i$가 적어도 하나 존재한다고 가정할 수 있다.

총 의석수 $m$의 가능한 최솟값을 출력한다.