Một kênh truyền hình giải trí phát sóng chương trình “Колесо Фортуны”. Trong trò chơi, người tham gia quay một bánh xe lớn được chia thành các phần hình quạt. Mỗi phần có ghi một số. Khi bánh xe dừng, một kim đặc biệt chỉ vào một phần. Số trong phần đó quyết định tiền thưởng của người chơi.

Một người tham gia trẻ tuổi nhận thấy bánh xe chậm dần khi quay vì kim chạm vào các chỗ nhô nằm giữa các phần. Nếu bánh xe quay với tốc độ góc $v$ độ mỗi giây và kim chạm chỗ nhô tiếp theo khi chuyển từ phần $X$ sang phần kế tiếp, tốc độ góc hiện tại giảm đi $k$ độ mỗi giây. Nếu $v\le k$, bánh xe không vượt được chướng ngại và dừng lại. Khi đó kim chỉ vào phần $X$.

Người tham gia trẻ tuổi chuẩn bị quay bánh xe. Biết thứ tự các phần, cậu muốn chọn tốc độ ban đầu sao cho khi bánh xe dừng, kim chỉ vào số lớn nhất có thể. Bánh xe có thể quay theo cả hai hướng và được cho tốc độ góc ban đầu từ $a$ đến $b$ độ mỗi giây.

Hãy viết chương trình tính tiền thưởng lớn nhất từ cách bố trí các số trong các phần, tốc độ góc ban đầu nhỏ nhất và lớn nhất, và mức giảm tốc khi vượt ranh giới giữa hai phần.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số nguyên $n$, số phần của bánh xe ($3\le n\le100$).

Dòng thứ hai chứa $n$ số nguyên dương, mỗi số không vượt quá $1000$, là các số ghi trong các phần. Các số được cho theo thứ tự các phần theo chiều kim đồng hồ. Ban đầu kim chỉ vào số thứ nhất.

Dòng thứ ba chứa ba số nguyên $a,b,k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).

Dữ liệu ra

Tệp đầu ra phải chứa một số nguyên: tiền thưởng lớn nhất.

Ví dụ

Dữ liệu vào 1

5
1 2 3 4 5
3 5 2

Dữ liệu ra 1

5

Dữ liệu vào 2

5
1 2 3 4 5
15 15 2

Dữ liệu ra 2

4

Dữ liệu vào 3

5
5 4 3 2 1
2 5 2

Dữ liệu ra 3

5

Ghi chú

Trong ví dụ thứ nhất, có thể chọn tốc độ ban đầu $3$ hoặc $4$ để kim vượt một ranh giới giữa các phần, hoặc tốc độ $5$ để kim vượt hai ranh giới. Với lựa chọn thứ nhất, quay theo một hướng cho tiền thưởng $2$, còn hướng ngược lại cho $5$. Với lựa chọn thứ hai, quay theo một hướng cho $3$, còn hướng kia cho $4$.

Trong ví dụ thứ hai, chỉ có một tốc độ góc ban đầu là $15$ độ mỗi giây. Khi đó kim vượt bảy ranh giới giữa các phần trong quá trình quay. Quay theo một hướng cho tiền thưởng $4$, còn hướng ngược lại cho $3$.

Cuối cùng, trong ví dụ thứ ba, tốc độ góc ban đầu tối ưu là $2$ độ mỗi giây. Kim không thể vượt bất kỳ ranh giới nào và tiền thưởng là $5$.

Ghi chú

Các lời giải đúng cho những kiểm thử có $1\le a\le b\le1000$ được chấm tối đa 50 điểm.