한 오락 채널에서 «Колесо Фортуны»라는 쇼를 방송한다. 게임에서 참가자들은 여러 구역으로 나누어진 큰 바퀴를 돌린다. 바퀴의 각 구역에는 수가 적혀 있다. 바퀴가 멈추면 특별한 화살표가 한 구역을 가리킨다. 그 구역에 적힌 수가 참가자의 상금을 결정한다.

어린 참가자는 바퀴가 회전하면서 느려지는 이유가 화살표가 구역 사이에 있는 바퀴의 돌기에 걸리기 때문임을 알아냈다. 바퀴가 초당 $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$점을 만점으로 평가된다.