Problem Description

Xiao Ming is a magician.

He has a sequence $A$ that can be enchanted.

He has two kinds of magic:

1. Spend $a$ mana, choose an interval $[l,r]$ in $A$, and add $1$ to all of $A_{l},A_{l+1}...A_{r}$.
2. Spend $b$ mana, choose an interval $[l,r]$ in $A$, and multiply all of $A_{l},A_{l+1}...A_{r}$ by $2$.

Now Xiao Ming wants to cast magic on the sequence $A$ several times so that there exists a sub-interval whose element sum is at least $s$. Please output the minimum mana cost that Xiao Ming needs to spend.

Input Format

The first line contains four integers $n,a,b,s$, representing the sequence length, the costs of the two kinds of magic, and the required sum.

The next line contains $n$ integers, representing the initial sequence.

Output Format

One integer, representing the minimum cost.

5 2 3 102
-3 -1 1 -2 0

17

Hint

[This problem uses bundled testdata.]

For $10\%$ of the testdata, $n \leq 5$, $|A_i|,s \le 100$.

For another $20\%$ of the testdata, $n = 10^3$.

For another $5\%$ of the testdata, $A_i \ge 0$.

For another $25\%$ of the testdata, $a,b \le 3$.

For $100\%$ of the testdata, $1 \leq n \leq 10^{5}$, $1 \leq a,b \leq 10^9$, $-10^{9} \leq A_{i} \leq 10^{9}$, $1 \leq s \leq 10^{9}$.

[Sample Explanation]:

For the sample, one of the best methods is to use Magic 1 once to change (1,4), use Magic 1 three times to change (2,5), and use Magic 2 three times to change (2,5).

-3 -1 1 -2 0

-2 0 2 -1 0
-2 1 3 0 1
-2 2 4 1 2
-2 3 5 2 3
-2 6 10 4 6
-2 12 20 8 12
-2 24 40 16 24

-2+24+40+16+24 >= 102

Translated by ChatGPT 5