#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long m1 = 1e9 + 7;
const long long m2 = 1e9 + 9;
const long long p1 = 402653189;
const long long p2 = 1610612741;
const long long LN = 61;
long long powermodm(long long x, long long n, long long M) {
  long long result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return result;
}
long long power(long long _a, long long _b) {
  long long _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
long long dx[4] = {-1, 1, 0, 0};
long long dy[4] = {0, 0, 1, -1};
long long n, A, R, M;
long long h[N], pref[N];
long long calc(long long val) {
  long long l = 0, r = n, ma = l;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (h[mid] <= val) {
      ma = max(ma, mid);
      l = mid + 1;
    } else
      r = mid - 1;
  }
  long long add = ma * val - pref[ma];
  long long dec = pref[n] - pref[ma] - (n - ma) * val;
  long long tans = 0;
  if (M < A + R) {
    long long tmp = min(add, dec);
    tans = tmp * M + (add - tmp) * A + (dec - tmp) * R;
  } else
    tans = add * A + dec * R;
  return tans;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long i, j;
  cin >> n >> A >> R >> M;
  for (i = 1; i <= n; i++) cin >> h[i];
  sort(h + 1, h + n + 1);
  for (i = 1; i <= n; i++) pref[i] = pref[i - 1] + h[i];
  long long l = 0, r = 1e9, mi = 1e18;
  while (l <= r) {
    long long diff = (r - l) / 3;
    long long mid1 = l + diff;
    long long mid2 = r - diff;
    long long val1 = calc(mid1);
    long long val2 = calc(mid2);
    if (val1 <= val2) {
      mi = min(mi, val1);
      r = mid2 - 1;
    } else {
      mi = min(mi, val2);
      l = mid1 + 1;
    }
  }
  cout << mi;
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

You have to restore the wall. The wall consists of N pillars of bricks, the height of the i-th pillar is initially equal to h_{i}, the height is measured in number of bricks. After the restoration all the N pillars should have equal heights.

You are allowed the following operations:

  * put a brick on top of one pillar, the cost of this operation is A;
  * remove a brick from the top of one non-empty pillar, the cost of this operation is R;
  * move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is M.



You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes 0.

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?

Input

The first line of input contains four integers N, A, R, M (1 ≤ N ≤ 10^{5}, 0 ≤ A, R, M ≤ 10^{4}) — the number of pillars and the costs of operations.

The second line contains N integers h_{i} (0 ≤ h_{i} ≤ 10^{9}) — initial heights of pillars.

Output

Print one integer — the minimal cost of restoration.

Examples

Input


3 1 100 100
1 3 8


Output


12


Input


3 100 1 100
1 3 8


Output


9


Input


3 100 100 1
1 3 8


Output


4


Input


5 1 2 4
5 5 3 6 5


Output


4


Input


5 1 2 2
5 5 3 6 5


Output


3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long m1 = 1e9 + 7;
const long long m2 = 1e9 + 9;
const long long p1 = 402653189;
const long long p2 = 1610612741;
const long long LN = 61;
long long powermodm(long long x, long long n, long long M) {
  long long result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return result;
}
long long power(long long _a, long long _b) {
  long long _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
long long dx[4] = {-1, 1, 0, 0};
long long dy[4] = {0, 0, 1, -1};
long long n, A, R, M;
long long h[N], pref[N];
long long calc(long long val) {
  long long l = 0, r = n, ma = l;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (h[mid] <= val) {
      ma = max(ma, mid);
      l = mid + 1;
    } else
      r = mid - 1;
  }
  long long add = ma * val - pref[ma];
  long long dec = pref[n] - pref[ma] - (n - ma) * val;
  long long tans = 0;
  if (M < A + R) {
    long long tmp = min(add, dec);
    tans = tmp * M + (add - tmp) * A + (dec - tmp) * R;
  } else
    tans = add * A + dec * R;
  return tans;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long i, j;
  cin >> n >> A >> R >> M;
  for (i = 1; i <= n; i++) cin >> h[i];
  sort(h + 1, h + n + 1);
  for (i = 1; i <= n; i++) pref[i] = pref[i - 1] + h[i];
  long long l = 0, r = 1e9, mi = 1e18;
  while (l <= r) {
    long long diff = (r - l) / 3;
    long long mid1 = l + diff;
    long long mid2 = r - diff;
    long long val1 = calc(mid1);
    long long val2 = calc(mid2);
    if (val1 <= val2) {
      mi = min(mi, val1);
      r = mid2 - 1;
    } else {
      mi = min(mi, val2);
      l = mid1 + 1;
    }
  }
  cout << mi;
  return 0;
}

```