As a ghost, stealth camouflage can protect you from the threat of ordinary troops. Unfortunately, stealth camouflage can't help you fill your stomach.
Recently you heard that there is a big plan on it, which seems to be to launch a large number of tactical nuclear missiles, and it is paid by piece. This can make you happy, you usually see those ordinary troops upset, not to mention that it can make you a lot of money now. So you start asking for information everywhere. You now know the following information:
1) The target of the attack this time is the group of Tadalin lunatics.You will face N goals.
2) You need to obtain the tactical nuclear missile before you can guide it.
3) According to your usual training data, it takes T seconds for you to complete the guidance of a nuclear bomb, which means you can't do other things in these T seconds. And every time you complete the guidance of a nuclear bomb, you will need to spend zi seconds to get to the next target location; in order to make more money, you sneak into the headquarters to get your own course of action, which means you Know in advance the time it takes to reach the i-th target location from the i-1th target point each time. (The 0th target point is the starting point)
4) The headquarters will distribute launch rights to ghosts that have reached the target location and are not guiding in a certain period of time every T seconds.
5) The time period for the headquarters to issue nuclear bombs is fixed, and the time to receive nuclear bombs satisfies \t{X≤tmodT≤Y}, t is the current moment, and X and Y are given data.
6) If the time reached the target location is not within the release time period, the headquarters will arrange for someone to distribute the nuclear bomb to you and deduct the overtime for your nuclear bomb.
7) The distribution of nuclear bombs is completed instantaneously, and each ghost must immediately guide it once it gets a nuclear bomb. And once the guidance is completed, the ghost immediately goes to the next target location. Once you reach the next target point, you must immediately apply for a nuclear bomb.
8) The overtime pay for each nuclear bomb is W.
9) You will start from the headquarters, which means that the time to reach the first target location as planned is x1.
In order to make more money, you found your good brother who was a machine gunner and borrowed a lot of adrenaline from him. Although this thing hurts your body, it is better than those 996 programmers. These adrenaline can help you reach the target location one second earlier, but due to your body restriction you can only use adrenaline once on the way to the next target point (even if you originally only need 1 second, you can also use adrenaline to make you Reach the next target location in an instant, after all, people and their physique cannot be generalized).
Now, it's time to make a plan and see how much you can earn.
输入描述:
In the first line of the input data, four integer numbers will be given, N, T, X, Y, W (1≤N≤3000, 3≤T≤1000000, 0≤X≤Y<T, 0≤W≤ 100)
The second line gives N integer numbers separated by spaces, where the i-th number represents xi. (1≤xi<T) Which is the time it takes you to reach the i-th target point from the i-1th target point. (The 0th target point is the starting point)
输出描述:
Output an integer number, representing the maximum value of overtime pay that can be earned.