問題文

btkさんは毎日ドーナツを食べています．
ある日，btkさんは N 日間ダイエットをすることを決意しました．
btkさんは毎日違うお店でドーナツを買っていて，ダイエット開始から i 日目に訪れるお店でドーナツを食べると$D_i$kg体重が増えることが分かっています． また，1 日ドーナツを食べるのをやめると，$A$kg痩せることができます.

しかし，ドーナツを食べない日が続くとストレスが溜まります．ここで，ストレス値というパラメータを定義します． ダイエット開始時点でのストレス値は0です．
1 日ドーナツを食べないとストレス値が 1 溜まり，1日の終了時にbtkさんの体重は$B\ast (\mathrm{ス}\mathrm{ト}\mathrm{レ}\mathrm{ス}\mathrm{値})$kg増加します． ドーナツを食べるとストレス値は 0 に戻ります．

各日において，ストレス値の変化後に体重が変化することに注意してください．

ダイエット開始前のbtkさんの体重を $W$ kgとしたとき，N 日間で何kgに痩せることができるでしょうか．

入力

$N$ $A$ $B$ $W$
$D_1$ $D_2$ ... $D_N$

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

出力

N日目終了後のbtkさんの体重の最小値を1行で出力してください．
終了時の体重はマイナスになることもあります．

サンプル

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