Problem Description

Xiao Lan has a magical furnace that can smelt ordinary metal O into a special metal X. The furnace has a property called the conversion rate $V$. $V$ is a positive integer, meaning that consuming exactly $V$ units of ordinary metal O can smelt one unit of special metal X. When the amount of ordinary metal O is less than $V$, smelting cannot continue.

Now you are given $N$ smelting records. Each record contains two integers $A$ and $B$, meaning that $A$ units of ordinary metal O were put in, and finally $B$ units of special metal X were produced. Each record is independent, which means any ordinary metal O left over from the previous record will not be carried over to the next smelting.

Based on these $N$ smelting records, please infer the minimum and maximum possible values of the conversion rate $V$. It is guaranteed that the testdata always has at least one solution.

Input Format

The first line contains an integer $N$, representing the number of smelting records.

Then follow $N$ lines, each containing two integers $A, B$, with the meaning described above.

Output Format

Output two integers, representing the minimum and maximum possible values of $V$, separated by a space.

3
75 3
53 2
59 2

20 25

Hint

Sample Explanation

When $V = 20$, we have: $\left\lfloor\frac{75}{20}\right\rfloor=3,\left\lfloor\frac{53}{20}\right\rfloor=2,\left\lfloor\frac{59}{20}\right\rfloor=2$, which satisfies all smelting records.

When $V = 25$, we have: $\left\lfloor\frac{75}{25}\right\rfloor=3,\left\lfloor\frac{53}{25}\right\rfloor=2,\left\lfloor\frac{59}{25}\right\rfloor=2$, which also satisfies all smelting records.

And we can no longer find a valid $V$ that is smaller than $20$ or larger than $25$.

Constraints

For $30\%$ of the test cases, $1 \leq N \leq 10^{2}$.

For $60\%$ of the test cases, $1 \leq N \leq 10^{3}$.

For $100\%$ of the test cases, $1 \leq N \leq 10^{4}$, $1 \leq B \leq A \leq 10^{9}$.

Lanqiao Cup 2023 Provincial Contest B Group, Problem C.

Translated by ChatGPT 5