Minimum Energy Cost

Each time, take the leftmost or the rightmost remaining bag. Taking a bag of weight w from the left has base cost w·X, and from the right w·Y. If this take and the previous one are both from the left, add El; if both are from the right, add Er; the first take has no consecutive cost. Take all the bags and find the minimum total energy.

输入格式

The first line contains n X Y El Er and the second line contains weights. On this site 1≤n≤200000, 0≤weights[i],X,Y,El,Er≤10^9. Output the exact integer, which may exceed 64 bits.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 4 4 19 1
42 3 99

输出：

576

样例 2

输入：

2 1 10 100 0
5 1

输出：

15

样例 3

输入：

3 0 0 5 7
1 1 1

输出：

0

样例说明

The answers are 576, 15 and 0. In the second example, take 5 from the left and 1 from the right, avoiding the extra cost of 100 for two left takes in a row.