Problem Description

Note: All sequence indices in this problem start from $0$.

Xiao R is a lovely girl who enjoys studying infinite sequences.

She defines an infinite sequence $b$ as wonderful if and only if there exists a natural number $k_0$ such that for all $k \geq k_0$, the sum of all numbers in $b$ with indices in the interval $[k_0, k]$ is non-negative (i.e., $\sum_{i=k_0}^k b_i \geq 0$). For example, the sequence $\alpha_i = i - 5$ is wonderful, taking $k_0 = 5$ meets the requirement; but $\beta_i = -i$ is not wonderful.

Currently, she only has a finite sequence $a$ of length $n$. She can perform any number of the following three operations:

1. Spend a cost of $p$, choose an integer $i$ ($0 \leq i < n$), and increase $a_i$ by one.
2. Spend a cost of $q$, choose an integer $i$ ($0 \leq i < n$), and delete $a_i$, updating $n$ to the new sequence length. The sequence cannot be emptied.
3. Spend a cost of $r$, choose two integers $i, j$ ($0 \leq i < j < n$), and swap $a_i$ with $a_j$.

She hopes to perform several operations to obtain an infinite sequence $b$ by concatenating infinitely many finite sequences $a$ (i.e., $b_i = a_{i \mod n}$), such that $b$ is wonderful. Please find the minimum cost.

Input Format

The first line contains four integers $n, p, q, r$.

The second line contains $n$ integers representing the sequence $a$.

Output Format

One line, an integer representing the minimum cost.

Sample Input and Output

Sample Input #1

5 1 2 5
2 -2 3 -3 -1

Sample Output #1

1

Sample Input #2

5 2 1 5
2 -2 3 -3 -1

Sample Output #2

1

Sample Input #3

5 1 1 1
0 1 2 3 4

Sample Output #3

0

Notes

Sample 1 Explanation

Spend a cost of $p = 1$ to increase $a_3$ by one, resulting in the sequence $b = [2, -2, 3, -2, -1, 2, -2, 3, -2, -1, \cdots]$ which is wonderful, taking $k_0 = 2$ meets the requirement.

It can be proven that no lower-cost solution exists.

Sample 2 Explanation

Spend a cost of $q = 1$ to delete $a_1$, resulting in the sequence $b = [2, 3, -3, -1, 2, 3, -3, -1, \cdots]$ which is wonderful, taking $k_0 = 0$ meets the requirement.

It can be proven that no lower-cost solution exists.

Data Range

This problem uses batched testing. Only by passing all test cases in the subtask and all dependent subtasks can you obtain the corresponding score.

For all data: $1 \leq n \leq 10^5$, $1 \leq p, q, r \leq 10^9$, $|a_i| \leq 10^9$.

• Subtask 1 (10 points): $n = 1$.
• Subtask 2 (10 points): $n \leq 10$. Dependent on Subtask 1.
• Subtask 3 (20 points): $|a_i| \leq 1$.
• Subtask 4 (20 points): $\sum |a_i| \leq 10^5$. Dependent on Subtask 3.
• Subtask 5 (40 points): No special restrictions. Dependent on Subtasks 1, 2, 3, and 4.

见题面 Input 部分

见题面 Output 部分