AT_agc040_d [AGC040D] Balance Beam

[problemUrl]: https://atcoder.jp/contests/agc040/tasks/agc040_d $ 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 $

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

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ 10^9 $ - 入力される値はすべて整数である． ### Sample Explanation 1 平均台 $ 2,1 $ の順に連結するとすぬけくんの勝率は $ 1/4 $ になり，これが最大です．