一个娱乐电视频道播出节目“Колесо Фортуны”。游戏中，参赛者转动一个分成若干扇区的大转轮。每个扇区内写着一个数。转轮停止后，一个专门的指针指向其中一个扇区。这个扇区中的数决定玩家获得的奖金。

一位年少的参赛者发现，转轮转动时会减速，这是因为指针会碰到转轮上位于扇区之间的凸起。如果转轮以每秒 $v$ 度的角速度转动，而指针从扇区 $X$ 移向下一个扇区时碰到下一个凸起，那么转轮当前的角速度会减少每秒 $k$ 度。如果 $v\le k$，转轮就无法越过这个障碍并停止。此时指针将指向扇区 $X$。

这位年少的参赛者准备转动转轮。他知道扇区在转轮上的排列顺序，希望给转轮一个合适的初始速度，使它停止后指针指向尽可能大的数。转轮可以向任意方向转动，初始角速度可以设为每秒 $a$ 到 $b$ 度。

请编写程序，根据扇区中各个数的排列、转轮的最小和最大初始角速度，以及越过扇区边界时的减速量，计算最大奖金。

输入格式

输入文件的第一行包含一个整数 $n$，表示转轮的扇区数量（$3\le n\le100$）。

输入文件的第二行包含 $n$ 个不超过 $1000$ 的正整数，表示各个扇区中的数。这些数按扇区的顺时针顺序给出。初始时，指针指向第一个数。

第三行包含三个整数 $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$。

第二个样例中，唯一可选的初始角速度是每秒 $15$ 度。此时转轮转动过程中指针将越过七个扇区边界。因此，向一个方向转动时奖金为 $4$，向相反方向转动时为 $3$。

最后，第三个样例中的最佳初始角速度为每秒 $2$ 度。此时指针完全无法越过扇区边界，奖金为 $5$。

说明

对于满足 $1\le a\le b\le1000$ 的测试，正确解法最多可获得 50 分。