「EZEC-5」魔法

小明是一个魔法师。 他有一个可以被施魔法的数列 $A$ 。 他有两种魔法： 1. 花费 $a$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $A_{l},A_{l+1}...A_{r}$ 全部 $+1$ 。 2. 花费 $b$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $A_{l},A_{l+1}...A_{r}$ 全部 $\times 2$ 。 现在小明想对 $A$ 序列施若干次魔法，使其存在一个子区间元素之和不小于 $s$ 。请求出小明需要花费的最小魔法值。

第一行四个整数 $n,a,b,s$，表示序列长度，两种魔法的代价，以及元素之和的要求。 接下来一行 $n$ 个整数，表示初始序列。

一个整数，表示最小花费。

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

17

【本题开启捆绑测试】 对于 $10\%$ 的数据，$n \leq 5， |A_i|,s\le 100$。 对于另外 $20\%$ 的数据，$n = 10^3$。 对于另外 $5\%$ 的数据，$A_i \ge 0$。 对于另外 $25\%$ 的数据，$a,b \le 3$。 对于 $100\%$ 的数据，$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}$ 【样例解释】： 对于样例，最佳方法之一为使用一次魔法 1 改变 (1,4)，三次魔法 1 改变 (2,5)，三次魔法 2 改变 (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 ```