Un canale televisivo di intrattenimento trasmette il programma «Колесо Фортуны». Durante il gioco, i partecipanti fanno girare una grande ruota divisa in settori. In ogni settore della ruota è scritto un numero. Quando la ruota si ferma, una freccia indica uno dei settori. Il numero in quel settore determina la vincita del giocatore.

Un giovane partecipante ha notato che la ruota rallenta durante la rotazione perché la freccia urta le sporgenze della ruota poste tra i settori. Se la ruota gira con velocità angolare $v$ gradi al secondo e la freccia, passando dal settore $X$ al successivo, urta un'altra sporgenza, la velocità angolare della ruota diminuisce di $k$ gradi al secondo. Se invece $v\le k$, la ruota non riesce a superare l'ostacolo e si ferma. In questo caso la freccia indica il settore $X$.

Il giovane partecipante sta per far girare la ruota. Conoscendo l'ordine dei settori, vuole imprimere alla ruota una velocità iniziale tale che, quando si ferma, la freccia indichi il numero più grande possibile. La ruota può girare in entrambe le direzioni e la sua velocità angolare iniziale può essere compresa tra $a$ e $b$ gradi al secondo.

Scrivete un programma che, dati i numeri nei settori, la velocità angolare iniziale minima e massima e la diminuzione di velocità a ogni passaggio tra due settori, calcoli la vincita massima.

Input

La prima riga del file di input contiene un intero $n$ — il numero di settori della ruota ($3\le n\le100$).

La seconda riga del file di input contiene $n$ interi positivi, ciascuno non superiore a $1000$ — i numeri scritti nei settori. I numeri sono elencati nell'ordine dei settori in senso orario. Inizialmente la freccia indica il primo numero.

La terza riga contiene tre interi: $a$, $b$ e $k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).

Output

Il file di output deve contenere un solo intero — la vincita massima.

Esempi

Input 1

5
1 2 3 4 5
3 5 2

Output 1

5

Input 2

5
1 2 3 4 5
15 15 2

Output 2

4

Input 3

5
5 4 3 2 1
2 5 2

Output 3

5

Nota

Nel primo esempio sono possibili le seguenti scelte: imprimere alla ruota una velocità iniziale di $3$ o $4$, in modo che la freccia superi un confine tra settori, oppure una velocità iniziale di $5$, che permette alla freccia di superare 2 confini tra settori. Nel primo caso, facendo girare la ruota in una direzione si ottiene una vincita di $2$, e nella direzione opposta una vincita di $5$. Nel secondo caso, facendo girare la ruota in una direzione la vincita è $3$, e nell'altra direzione è $4$.

Nel secondo esempio è possibile una sola velocità angolare iniziale: $15$ gradi al secondo. In questo caso, durante la rotazione la freccia supera sette confini tra settori. Se la ruota gira in una direzione, la vincita è $4$; se gira nella direzione opposta, è $3$.

Infine, nel terzo esempio la velocità angolare iniziale ottimale è $2$ gradi al secondo. In questo caso la freccia non può superare alcun confine tra settori e la vincita è $5$.

Nota

Le soluzioni corrette per i test in cui $1\le a\le b\le1000$ saranno valutate su 50 punti.