情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』
JOI 国で美術展が行われることになった．美術展では，国中から集まった様々な美術品が展示される予定である．
展示される美術品の候補として，N 点の美術品が集まった．これらの美術品には1, 2, ..., N の番号が付けられている．それぞれの美術品には大きさと価値と呼ばれる値が定まっている．美術品i (1 \leq i \leq N) の大きさはA_i，価値はB_i である．
美術展では，これらの美術品のうちから1 点以上を選んで展示する．美術展の会場は十分に広く，N 点の美術品すべてを展示することも可能である．しかし，JOI 国の人々の美的感覚のため，美術品の間で大きさの差があまり大きくならないように展示する美術品を選びたい．一方，できるだけ価値の大きい美術品を多く展示したい．そのため，次の条件を満たすように展示する美術品を選ぶことにした：
展示される美術品の候補の個数と，それぞれの美術品の大きさと価値が与えられたとき，S - (A_{max} - A_{min})の最大値を求めよ．
標準入力から以下の入力を読み込め．
標準出力に，S - (A_{max} - A_{min}) の最大値を1 行で出力せよ．
すべての入力データは以下の条件を満たす．
3 2 3 11 2 4 5
6
この入力例では，展示される美術品の候補が3 点ある．それぞれの美術品の大きさ，価値は次の通りである．
この場合，美術品1 と美術品3 を展示するために選ぶと，次のようにしてS - (A_{max} - A_{min}) = 6 となる．
S - (A_{max} - A_{min}) を7 以上にすることは不可能なので，6 を出力する．
6 4 1 1 5 10 3 9 1 4 2 5 3
7
15 1543361732 260774320 2089759661 257198921 1555665663 389548466 4133306295 296394520 2596448427 301103944 1701413087 274491541 2347488426 912791996 2133012079 444074242 2659886224 656957044 1345396764 259870638 2671164286 233246973 2791812672 585862344 2996614635 91065315 971304780 488995617 1523452673 988137562
4232545716