19375번 - Election 다국어

문제

An election was held today. A total of $n$ parties, numbered 1ドル$ through $n,ドル has participated in this election, and $m$ slots were distributed among the parties based on the number of votes each party got. The following algorithm was used for slot distribution:

Suppose that the parties 1,ドル 2, \ldots, n$ got $c_1, c_2, \ldots, c_n$ votes, respectively. Let $s = c_1 + c_2 + \ldots + c_n$. First, for each $i,ドル $\lfloor \frac{c_i}{s} \cdot m \rfloor$ slots are distributed to the party $i$. Then, the remaining slots are distributed from the parties with the larger value of the fractional part of $\frac{c_i}{s} \cdot m,ドル one slot per party. In case of a tie, the lower-indexed party has the priority.

You have the following information:

• The parties 1,ドル 2, \ldots, n$ got exactly $a_1, a_2, \ldots, a_n$ votes, respectively.
• The parties 1,ドル 2, \ldots, n$ got at least $b_1, b_2, \ldots, b_n$ slots, respectively.

Compute the minimum possible number of total slots $m$.

입력

The first line of input contains one integer $n$ (1ドル \le n \le 100$). Then $n$ lines follow, each contains a pair of integers $a_i$ and $b_i$ (1ドル \le a_i \le 1000,ドル 0ドル \le b_i \le 10^9$). You may assume that there exists at least one $i$ such that $b_i \ge 1$.

출력

Print the minimum possible number of total slots $m$.

제한

힌트