贪心 · 例8-国王的游戏
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题转译自 [NOIP2012 提高组] 国王的游戏 。
\hspace{15pt}国王邀请 n 位大臣来玩一个有奖游戏。首先，他在自己和每个大臣在左、右手上面分别写下一个整数 l 和 r 。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，第 i 位大臣可以获得金币数量：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果；换句话说，即：
\displaystyle \left\lfloor \frac{\prod_{j=0}^{i-1} l_j}{r_i} \right\rfloor = \left\lfloor \frac{l_0 \times l_1 \times \cdots \times l_{i-1}}{r_i} \right\rfloor
\hspace{15pt}国王不希望某一个大臣获得特别多的奖赏，所以他想重新安排大臣的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。
\hspace{15pt}注意，国王的位置始终在队伍的最前面。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 10^3\right) 代表大臣的人数。 
\hspace{15pt}第二行输入两个整数 l_0, r_0 \left(0 < l_0, r_0 < 10^4\right) 代表国王左右手上的数字。 
\hspace{15pt}此后 n 行，第 i 行包含两个整数 l_i, r_i \left(0 < l_i, r_i < 10^4\right) 代表每个大臣左右手上的数字。

输出描述:

\hspace{15pt}在一行上输出一个整数，代表重新排列后，队伍中获奖赏最多的大臣所获得的金币数。
示例1

输入

复制 
2
1 1
4 5
1 4

输出

复制 
0

说明

\hspace{15pt}如果从前到后依次为第一、二位大臣，此时：
\hspace{23pt}\bullet\,第一位大臣将获得 \left\lfloor \tfrac{1}{5} \right\rfloor = 0 个金币；
\hspace{23pt}\bullet\,第二位大臣将获得 \left\lfloor \tfrac{1 \times 4}{4} \right\rfloor = 1 个金币。

\hspace{15pt}如果从前到后依次为第二、一位大臣，此时：
\hspace{23pt}\bullet\,第一位大臣将获得 \left\lfloor \tfrac{1}{4} \right\rfloor = 0 个金币；
\hspace{23pt}\bullet\,第二位大臣将获得 \left\lfloor \tfrac{1 \times 1}{6} \right\rfloor = 0 个金币。

\hspace{15pt}因此，国王重新排列大臣的顺序后，队伍中获奖赏最多的大臣所获得的最少金币数为 0 ，此时第二位大臣在前、第一位大臣在后。
示例2

输入

复制 
3
1 1
2 3
7 4
4 6

输出

复制 
2

说明

\hspace{15pt}在这个样例中：
\hspace{23pt}\bullet\,按一、二、三这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ； 
\hspace{23pt}\bullet\,按一、三、二这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ； 
\hspace{23pt}\bullet\,按二、一、三这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ； 
\hspace{23pt}\bullet\,按二、三、一这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 ； 
\hspace{23pt}\bullet\,按三、一、二这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ； 
\hspace{23pt}\bullet\,按三、二、一这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 ；
\hspace{15pt}因此，奖赏最多的大臣最少获得 2 个金币。

备注: