An entertainment television channel broadcasts the show “Колесо Фортуны”. During the game, contestants spin a large wheel divided into sectors. Each sector contains a number. After the wheel stops, a special pointer points to one of the sectors. The number in that sector determines the player's winnings.

A young contestant noticed that the wheel slows down as it spins because the pointer catches on protrusions on the wheel between sectors. If the wheel is rotating at an angular speed of $v$ degrees per second and the pointer catches on another protrusion while moving from sector $X$ to the next sector, the wheel's current angular speed decreases by $k$ degrees per second. If $v\le k$, the wheel cannot overcome the obstacle and stops. In this case, the pointer will point to sector $X$.

The young contestant is about to spin the wheel. Knowing the order of the sectors, he wants to give the wheel an initial speed such that, after it stops, the pointer points to the largest possible number. The wheel can be spun in either direction, with an initial angular speed from $a$ to $b$ degrees per second.

Write a program that calculates the maximum winnings given the arrangement of the numbers in the sectors, the minimum and maximum initial angular speeds of the wheel, and the amount by which the wheel slows down when crossing a sector boundary.

Input

The first line of the input file contains an integer $n$, the number of sectors of the wheel ($3\le n\le100$).

The second line of the input file contains $n$ positive integers, each not exceeding $1000$: the numbers written in the sectors of the wheel. The numbers are given in clockwise sector order. Initially, the pointer points to the first number.

The third line contains three integers $a$, $b$, and $k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).

Output

The output file must contain one integer: the maximum winnings.

Examples

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

Note

In the first example, the following options are possible: the wheel can be given an initial speed of $3$ or $4$, which allows the pointer to cross one sector boundary, or an initial speed of $5$, which allows the pointer to cross two sector boundaries. In the first option, spinning the wheel in one direction gives winnings of $2$, while spinning it in the opposite direction gives $5$. In the second option, spinning the wheel in one direction gives winnings of $3$, while spinning it in the other direction gives $4$.

In the second example, only one initial angular speed is possible: $15$ degrees per second. In this case, the pointer crosses seven sector boundaries as the wheel spins. Spinning it in one direction gives winnings of $4$, while spinning it in the opposite direction gives $3$.

Finally, in the third example, the optimal initial angular speed is $2$ degrees per second. In this case, the pointer cannot cross any sector boundary, and the winnings are $5$.

Note

Correct solutions for tests in which $1\le a\le b\le1000$ will be scored out of 50 points.