ある娯楽テレビチャンネルは「Колесо Фортуны」という番組を放送しています。ゲーム中、参加者は扇形の区画に分けられた大きな輪を回します。各区画には数が書かれています。輪が停止すると、特別な指針が一つの区画を指します。その区画の数が参加者の賞金を決めます。

若い参加者は、輪の回転中に指針が区画の間にある突起に当たるため、輪が減速することに気づきました。輪が毎秒 $v$ 度の角速度で回転していて、指針が区画 $X$ から次の区画へ移るときに次の突起に当たると、現在の角速度は毎秒 $k$ 度だけ減少します。$v\le k$ の場合は輪が障害を越えられず停止します。この場合、指針は区画 $X$ を指します。

若い参加者は輪を回そうとしています。区画の順序を知っているので、輪が停止したときに指針ができるだけ大きな数を指すような初速度を与えたいと考えています。輪はどちらの方向にも回すことができ、初期角速度は毎秒 $a$ 度から $b$ 度までにできます。

区画に書かれた数の配置、最小および最大の初期角速度、区画の境界を越えるときの減速量から、最大の賞金を求めるプログラムを書いてください。

入力

入力ファイルの最初の行には整数 $n$ が含まれます。これは輪の区画数です（$3\le n\le100$）。

入力ファイルの 2 行目には、各区画の数を表す $n$ 個の正の整数が含まれます。各数は $1000$ 以下です。数は区画の時計回りの順に与えられます。最初、指針は最初の数を指しています。

3 行目には三つの整数 $a,b,k$ が含まれます（$1\le a\le b\le10^9$、$1\le k\le10^9$）。

出力

出力ファイルには最大の賞金を表す整数を一つ出力してください。

入出力例

入力 1

5
1 2 3 4 5
3 5 2

出力 1

5

入力 2

5
1 2 3 4 5
15 15 2

出力 2

4

入力 3

5
5 4 3 2 1
2 5 2

出力 3

5

注記

最初の例では、初速度を $3$ または $4$ にすると指針が区画の境界を一つ越え、初速度を $5$ にすると二つ越えます。前者の場合、一方の方向に回すと賞金は $2$、反対方向に回すと $5$ です。後者の場合、一方の方向なら賞金は $3$、もう一方なら $4$ です。

2 番目の例で選べる初期角速度は毎秒 $15$ 度だけです。この場合、回転中に指針は区画の境界を七つ越えます。一方の方向に回すと賞金は $4$、反対方向に回すと $3$ です。

最後に、3 番目の例の最適な初期角速度は毎秒 $2$ 度です。この場合、指針は区画の境界を全く越えられず、賞金は $5$ です。

注記

$1\le a\le b\le1000$ を満たすテストに対する正しい解法は最大 50 点で評価されます。