配点 : $1100$ 点

問題文

$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$ としてください．

制約

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

入力

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

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

出力

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

2
3 2
1 2

1 4

平均台 $2,1$ の順に連結するとすぬけくんの勝率は $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