問題文

ここに N 個の箱があり、i 個目の箱には A_i 個のビー玉が入っています。

Cyanmond 君は、箱に入っているビー玉の数をなるべく均等にするために次の行動をします。

• まず X 個の箱を選ぶ。選んだ全ての箱に B 個のビー玉を追加する。
• その後 Y 個の箱を選ぶ。選んだ全ての箱に C 個のビー玉を追加する。

この行動を終えた後、箱に入っているビー玉の個数の最大値を D、最小値を E とします。適切に箱を選んだ時の D - E として考えられる最小値を求めてください。

制約

• 2 \leq N \leq 2.5 \times 10^5
• 0 \leq X,Y \leq N
• 1 \leq A_{i},B,C \leq 10^{18}
• 入力は全て整数

入力例 1

5 1 2
7 3
17 7 13 16 18

出力例 1

2

例えば、次のような入れ方が考えられます。

• 2 個目の箱に 7 個のビー玉を追加した後、2 個目の箱と 3 個目の箱に 3 個のビー玉を追加する。

この場合、最終的なビー玉の個数の最大値は 18、最小値は 16 となり、D-E は 2 です。

D-E を 2 より小さくする選び方は存在しないので、2 を出力します。

入力例 2

3 2 2
50 100
10 10 15

出力例 2

95

原案: Cyanmond