Magical Array Transformation

Little Ming is a magician. He possesses a magical sequence \(A\) and two types of spells. The spells are described as follows:

• Spell 1: For a cost of \(a\) magic points, choose an interval \([l, r]\) in \(A\) and add \(1\) to each element in that interval, i.e. \(A_l, A_{l+1}, \dots, A_r\) become \(A_l+1, A_{l+1}+1, \dots, A_r+1\).
• Spell 2: For a cost of \(b\) magic points, choose an interval \([l, r]\) in \(A\) and multiply each element in that interval by \(2\), i.e. \(A_l, A_{l+1}, \dots, A_r\) become \(2\cdot A_l, 2\cdot A_{l+1}, \dots, 2\cdot A_r\).

Little Ming wants to cast a sequence of spells so that there exists at least one contiguous subarray of \(A\) whose sum is at least \(s\). Determine the minimum total magic cost required to achieve this goal.

Note: The spells can be applied in any order and any number of times (possibly zero). You may assume that applying spells on a single element (i.e. choosing an interval where \(l=r\)) is allowed.

Observation: It is always optimal to try to boost a single element to become at least \(s\) since if one element is at least \(s\) then the subarray consisting of that element has a sum \(\ge s\). For an element with initial value \(x\), let the minimum cost to achieve a value \(\ge s\) be \(f(x)\). Then:

[ f(x)= \begin{cases} 0, & \text{if} \ x \ge s, \ (s-x)\cdot a, & \text{if} \ x = 0, \ \min\bigl((s-x)\cdot a,; b + f(2x)\bigr), & \text{if} ; 0 < x < s. \end{cases} ]

The answer to the problem is \(\min_{1 \le i \le n} f(A_i)\).

inputFormat

The input consists of two lines:

The first line contains four space-separated integers: \(n\) (the size of the array), \(a\) (the cost to add \(1\) to an interval), \(b\) (the cost to multiply an interval by \(2\)), and \(s\) (the target sum threshold).

The second line contains \(n\) space-separated integers representing the array \(A\): \(A_1, A_2, \dots, A_n\).

outputFormat

Output one integer, which is the minimum magic cost required so that there exists at least one contiguous subarray of \(A\) whose sum is at least \(s\).

sample

3 1 10 10
1 2 3

7