問題文

NN 枚のせんべいがあります。
やきとりくんは、この中から 22 枚を選んでシカにせんべいを与えようとしています。
i(1iN)i \: (1 \leq i \leq N) 個目のせんべいを与えると、シカのスピードを AiA_{i}、スタミナを BiB_{i} だけ上昇させることができます。
また、せんべいを与える前のシカのスピードとスタミナは全て 00 です。
やきとりくんは、スピードとスタミナの最小値を戦闘力と定義しました。
せんべいを与えた後のシカの戦闘力としてあり得る最大値を求めてください。

制約

  • 2N1052 \leq N \leq 10^{5}
  • 1Ai,Bi109(1iN)1 \leq A_{i}, B_{i} \leq 10^{9} \: (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N
A1 B1
A2 B2
... ...
AN BN

出力

問題の答えを一行に出力せよ。

入出力例

入力例1
3
25 50
100 1
45 30
出力例1
70

11 番目と 33 番目のせんべいをシカに与えることによって、スピードは 7070、スタミナは 8080 となるため戦闘力は 7070 となり、これが最大です。

入力例2
12
246 764
271 548
706 437
763 954
974 106
357 77
206 150
907 883
21 150
762 763
799 19
610 868
出力例2
1670

提出


Go (1.21)