题目描述

$1$ から $N$ までの番号がついた $N$ 個の平均台があります． どの平均台の長さも $1$ メートルです． すぬけくんが平均台 $i$ の上をあるくスピードは $1$ 秒あたり $1/A_i$ メートルです． また，りんごさんが平均台 $i$ の上をあるくスピードは $1$ 秒あたり $1/B_i$ メートルです．

すぬけくんとりんごさんが，以下のゲームを行います．

• まず，すぬけくんが $N$ 個の平均台を好きな順序で横一列に連結し，長さ $N$ メートルの平均台を作る．
• すぬけくんはこの平均台の左端からスタートする． りんごさんはこの平均台の上で一様ランダムに選ばれた一点からスタートする． $2$ 人は同時にスタートし，平均台の右端を目指して進む。
• すぬけくんの勝利条件は，りんごさんが平均台の右端に到着する前にりんごさんに追いつくことである． つまり，すぬけくんとりんごさんの位置が同じになる瞬間があればすぬけくんの勝ち，そうでないならりんごさんの勝ちである．

すぬけくんが勝率を最大化するように平均台を並べたときの勝率を求めてください．

なお，この問題の答えは有理数になります． そこで，答えを既約分数 $P/Q$ として表したときの $P,Q$ を求めてください． ただし，答えが $0$ の時は $P=0,Q=1$ としてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

すぬけくんの勝率の最大値を表す既約分数の分子と分母を出力せよ．

题目大意

给定 $n$ 个长度为 $1$ 的石板，Alice 通过第 $i$ 个石板时的速度为 $\frac{1}{A_i}$，Bob 通过第 $i$ 个石板时的速度为 $\frac{1}{B_i}$ 。

现在他们进行这样的一个游戏：

• Alice 以任意顺序排列这 $n$ 个石板，并构成一个大石板，然后他站在这个大石板的最左边往右跑。
• Bob 在这长度为 $n$ 的大石板上均匀随机选择一个点（注意不一定是整点）然后从这个点开始往右跑。
• 注意两者同时出发，如果在途中 Alice 抓到了 Bob （即在 Bob 未到达终点时抓到了他），则称 Alice win，否则说 Bob win

问 Alice 如何排列这 $n$ 个石板，可以使得 Alice win 的概率最大，最大是多少？答案输出一个真分数，即 $P/Q$ 的性质，特别的，如果 $P = 0$，则 $Q=1$ 。

保证 $1\le n\le 10^5,1\le A_i,B_i\le 10^9$

translated by Soulist

2
3 2
1 2

1 4

4
1 5
4 7
2 1
8 4

1 2

3
4 1
5 2
6 3

0 1

10
866111664 178537096
705445072 318106937
472381277 579910117
353498483 865935868
383133839 231371336
378371075 681212831
304570952 16537461
955719384 267238505
844917655 218662351
550309930 62731178

697461712 2899550585

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i,B_i\ \leq\ 10^9$
• 入力される値はすべて整数である．

Sample Explanation 1

平均台 $2,1$ の順に連結するとすぬけくんの勝率は $1/4$ になり，これが最大です．