Restorer Distance

Problem Source

CF 1355E

Problem Description

You are given $N$ numbers $h_1, h_2, \dots, h_N$. You need to perform some operations to make all of them equal. The operations are:

• Increase any number by $1$, at cost $A$;
• Decrease any number by $1$, at cost $R$;
• Decrease one number by $1$ and increase another number by $1$, at cost $M$.

What is the minimum total cost to make all numbers equal?

Input Format

The first line contains 4 integers $N, A, R, M$.

The next line contains $N$ integers $h_1, h_2, \dots, h_N$.

Output Format

One line containing an integer: the minimum cost.

Sample Input

3 1 100 100
1 3 8

Sample Output

12

Constraints

For $100\%$ of the data, $1 \leq N \leq 10^5, 0 \leq A, R, M \leq 10^4, 0 \leq a_i \leq 10^9$.