Wheel of Fortune
The entertainment TV channel features the show "Wheel of Fortune". In this game, participants spin a large wheel divided into multiple sectors, each marked with a number. When the wheel stops, a pointer indicates one of these sectors, and the number in that sector determines the player's winnings.
A young contestant has observed that the wheel slows down as it spins because the pointer catches on protrusions located between the sectors. If the wheel spins with an angular speed of v degrees per second and the pointer catches on a protrusion while moving from sector X to the next, the wheel's speed decreases by k degrees per second. If v is less than or equal to k, the wheel cannot overcome the protrusion and stops, leaving the pointer on sector X.
The young contestant is preparing to spin the wheel and wants to choose an initial speed that ensures the pointer stops at the sector with the highest number. The wheel can be spun in either direction, with an initial angular speed ranging from a to b degrees per second.
Your task is to write a program that, given the sequence of numbers on the wheel's sectors, the minimum and maximum possible initial angular speeds, and the deceleration rate when crossing sector boundaries, calculates the maximum possible winnings.
Input
The first line of the input contains an integer n — the number of sectors on the wheel (3 ≤ n ≤ 100).
The second line contains n positive integers, each not exceeding 1000 — the numbers written on the wheel's sectors. These numbers are listed in the order of the sectors, moving clockwise. Initially, the pointer points to the first number.
The third line contains three integers: a, b, and k (1 ≤ a ≤ b ≤ 10^9, 1 ≤ k ≤ 10^9).
Output
The output should be a single integer — the maximum winnings possible.