一個娛樂電視頻道播出節目「Колесо Фортуны」。遊戲中，參賽者轉動一個分成若干扇區的大轉輪。每個扇區內寫著一個數。轉輪停止後，一個專門的指針指向其中一個扇區。這個扇區中的數決定玩家獲得的獎金。

一位年少的參賽者發現，轉輪轉動時會減速，這是因為指針會碰到轉輪上位於扇區之間的凸起。如果轉輪以每秒 $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 分。