Making an Infinite Sequence Wonderful

Consider an array (a) of length (n) with indices starting at (0). We say that the infinite periodic sequence (b) defined as [ b_{i}=a_{i \bmod n} ] is wonderful if and only if there exists an index (k_{0}) (a natural number) such that for every (k\ge k_{0}) we have [ \sum_{i=k_{0}}^{k} b_{i} \ge 0. ] It can be shown that for a periodic sequence of period (a) the necessary and sufficient condition for being wonderful is that the total sum [ S=\sum_{i=0}^{n-1} a_i \ge 0 ] (i.e. (a) has nonnegative sum).

Initially you are given a finite array (a) of length (n) (which may contain negative numbers). You are allowed to perform the following operations any number of times:

1. Increase: Choose an index (i) ((0\le i<n)) and increase (a_i) by (1) at a cost of (p). This increases the overall sum by (1).
2. Deletion: Choose an index (i) ((0\le i<n)) and remove (a_i) from the array at a cost of (q). (Note: You are not allowed to delete all elements; the final array must be nonempty.)
3. Swap: Choose two indices (i,j) (with (0\le i<j<n)) and swap (a_i) and (a_j) at a cost of (r).

After you perform some operations the resulting finite array (a') is repeated infinitely (i.e. (b_i=a'_{i \bmod n'}) where (n') is the new length) and must be wonderful. Since for any periodic sequence the wonderful property is equivalent to having nonnegative total sum, your goal is to modify (a) (using any sequence of operations) so that the final array has a nonnegative sum.

Be careful: although swapping does not change the multiset of numbers and hence not the sum, it comes with a cost (r). However, it turns out that by an appropriate cyclic rotation (which is free conceptually) any array with nonnegative total sum gives rise to a wonderful infinite sequence. Thus, the only challenge is to achieve (\sum a' \ge 0) at minimum total cost.

A natural approach is to adjust the array element–by–element. For any element (a_i):

• If (a_i \ge 0) no change is necessary.
• If (a_i<0) you have three choices:
  • Do nothing (leave (a_i) as is). It will contribute (a_i (<0)) to the sum and might force you to pay extra using the Increase operation later to compensate for the deficit.
  • Increase (a_i) by (-a_i) to make it (0) at a cost of (p\cdot(-a_i)).
  • Delete (a_i) at a cost of (q).

Since doing nothing will eventually force you to add exactly (p\cdot(-a_i)) if the overall sum is negative, the effective cost for turning a negative into a nonnegative contribution is essentially \n(\min\bigl(p\cdot(-a_i),;q\bigr)) if there is no surplus from the other (nonnegative) elements. However, if the sum of the nonnegative numbers (and those negatives you do not repair) is already high, you may not need to fix a small negative value at all.

More formally, let (P=\sum_{a_i\ge0} a_i). For each negative (a_i<0) let [ d_i=-a_i>0. ] Now, if you choose to leave such an element unchanged its contribution is (-d_i) (forcing you to later increase some element by (d_i) at a cost of (p\cdot d_i) to recover the deficit), but if you either increase it immediately (i.e. fix it) or delete it, its contribution becomes (0), at a cost of (p\cdot d_i) or (q) respectively. Hence, for each negative (a_i) you must decide between keeping it (and possibly paying a global cost of (p\cdot\max(0, -(P+\mbox{sum of kept negatives})))) versus paying (\min(p\cdot d_i,q)) to remove its negative effect.

One may show that an optimal strategy is as follows:

1. For every element (a_i\ge0), keep it.
2. For every element (a_i<0):
   • If (p\cdot(-a_i)>q), delete it (cost (q)).
   • Otherwise, keep it without immediate increase.
3. After these choices, let the sum of the remaining array (i.e. (P) plus the kept negatives) be (S'). If (S' < 0), perform additional Increase operations (on any one element) to add (-S') at a cost of (p\cdot(-S' )).
4. One extra detail: if all elements are negative and your above decisions would delete all numbers, then you must force keeping (and fixing) at least one negative (choose the one that minimizes (p\cdot(-a_i))).

Your task is to compute the minimum cost required to achieve (\sum a' \ge 0).

Note that the swap operation (at cost (r)) is available but, as argued above, since any array with (\sum a'\ge0) can be made wonderful by a cyclic rotation, there is no need to pay extra cost for swapping if you take an optimal strategy.

Formally, given (n, p, q, r) and the array (a), compute the minimal total cost so that after a sequence of Increase, Deletion and Swap operations the final array (of positive length) has a nonnegative sum.

inputFormat

The first line contains four integers (n,; p,; q,; r) ((1 \le n \le 10^5,; 1 \le p,q,r \le 10^9)) representing the length of the array and the costs of Increase, Deletion, and Swap operations respectively. The second line contains (n) integers (a_0,a_1,\dots,a_{n-1}) (( -10^9 \le a_i \le 10^9)) representing the array.

outputFormat

Output a single integer — the minimum total cost required so that, after operations, if the final array is repeated infinitely, the resulting sequence is wonderful.

sample

2 10 20 5
10 -1

0

</p>