枚のせんべいがあります。
やきとりくんは、この中から 枚を選んでシカにせんべいを与えようとしています。
個目のせんべいを与えると、シカのスピードを 、スタミナを だけ上昇させることができます。
また、せんべいを与える前のシカのスピードとスタミナは全て です。
やきとりくんは、スピードとスタミナの最小値を戦闘力と定義しました。
せんべいを与えた後のシカの戦闘力としてあり得る最大値を求めてください。
N A1 B1 A2 B2 ... ... AN BN
問題の答えを一行に出力せよ。
3 25 50 100 1 45 30
70
番目と 番目のせんべいをシカに与えることによって、スピードは 、スタミナは となるため戦闘力は となり、これが最大です。
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
1670