Problem Statement

btk eats donuts every day.
One day, btk decided to go on a diet for N days.
btk buys donuts at a different shop each day, and it is known that eating a donut from the shop visited on day i of the diet increases btk's weight by $D_i$kg. Also, by skipping donuts for 1 day, btk can lose $A$kg.

However, consecutive days without donuts build up stress. Here, we define a parameter called the stress value. The stress value at the start of the diet is 0.
For each 1 day without eating a donut, the stress value increases by 1, and at the end of that day btk's weight increases by $B*(ストレス値)$kg, where ストレス値 denotes the stress value. Eating a donut resets the stress value to 0.

Note that on each day, the weight changes after the stress value changes.

Given that btk's weight before the start of the diet is $W$ kg, how many kg can btk slim down to over the N days?

Input

$N$ $A$ $B$ $W$
$D_1$ $D_2$ ... $D_{N}$

$1 \le N \le 3*10^5$
$0 \le A,B,W \le 10^6$
$0 \le D_i \le 10^6$

Output

Print on one line the minimum possible weight of btk after the end of day N.
The final weight may be negative.

Sample

2 5 2 10
0 6

6

5 1 0 50
1 2 3 4 5

45

7 4 6 56
10 9 7 17 8 3 7

88