题目描述

小明是一个魔法师。

他有一个可以被施魔法的数列 $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