#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline string bin(T n, int pos = 62) {
  string s;
  T i, one = 1, two = 2;
  for (i = (one << (pos - 1)); i > 0; i = (i >> 1)) s += ((n & i) ? "1" : "0");
  return s;
}
int lsb(unsigned int v) {
  int r;
  static const int MultiplyDeBruijnBitPosition[32] = {
      0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9};
  r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
  return r + 1;
}
template <class T>
inline int msb(T n) {
  return (n == 0) ? 0 : (1 + msb(n >> 1));
}
template <class T>
inline T getbit(T n, int pos) {
  return ((n & (1 << pos)) ? 1 : 0);
}
template <class T>
inline int countbit(T n) {
  return (n == 0) ? 0 : (1 + countbit(n & (n - 1)));
}
template <class T>
inline void setbit(T &n, int p) {
  n = n | (1LL << p);
}
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
bool isequal(vector<int> a, vector<int> b) {
  for (int i = 0; i < (a.size()); i++)
    if (a[i] != b[i]) return false;
  return true;
}
template <class T>
bool allequal(vector<T> a) {
  sort(a.begin(), a.end());
  return a[0] == a[a.size() - 1];
}
template <class T1, class T2>
void printpairs(vector<pair<T1, T2>> p) {
  for (auto t : p) {
    cout << "(" << t.first << " " << t.second << ")  ";
  }
  cout << endl;
}
template <class T>
void printvec(vector<T> a) {
  for (int i = 0; i < (a.size()); i++) cout << a[i] << " ";
  cout << endl;
}
void printarray(int *a, int n) {
  for (int i = 0; i < (n); i++) cout << *(a + i) << " ";
  cout << endl;
}
template <typename T>
void printmatrix(vector<vector<T>> a, int n, int m, int width = 5) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << setw(width) << a[i][j];
    }
    cout << endl;
  }
}
template <typename T>
void readmatrix(vector<vector<T>> &a, int n, int m) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
}
template <class T>
void printsubarray(vector<T> a, int start, int end) {
  if (start < 0 or end > a.size() - 1) cout << "Out of bounds" << endl;
  for (int i = start; i <= end; i++) cout << a[i] << " ";
  cout << endl;
}
bool isprime(int n) {
  if (n < 2) return false;
  if (n == 2) return true;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void split(const string &s, char c, vector<string> &result) {
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) result.push_back(x);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << ' ';
  err(++it, args...);
}
void yup() { cout << "Yes" << endl; }
void nope() { cout << "No" << endl; }
void Yup() { cout << "YES" << endl; }
void Nope() { cout << "NO" << endl; }
template <typename T>
void readvec(vector<T> &a, int size) {
  T tmp;
  a.clear();
  for (int i = 0; i < (size); i++) {
    cin >> tmp;
    a.push_back(tmp);
  }
}
int n, a, r, m;
vector<int> h;
vector<long long> prefix;
vector<long long> postfix;
void precompute() {
  prefix = vector<long long>(n + 2, 0LL);
  postfix = vector<long long>(n + 2, 0LL);
  for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + (long long)h[i - 1];
  }
  for (int i = n; i > 0; i--) {
    postfix[i] = postfix[i + 1] + (long long)h[i - 1];
  }
}
long long cost(int f) {
  long long cur = 0;
  int idx = lower_bound(h.begin(), h.end(), f) - h.begin();
  long long need = ((long long)idx * (long long)f) - prefix[idx];
  long long have = postfix[idx + 1] - ((long long)(n - idx) * (long long)f);
  if (a + r > m) {
    if (have >= need) {
      cur = m * need + (have - need) * r;
    } else {
      cur = m * have + (need - have) * a;
    }
  } else {
    cur = have * r + need * a;
  }
  return cur;
}
void solvecase() {
  int mid;
  cin >> n >> a >> r >> m;
  readvec(h, n);
  sort(h.begin(), h.end());
  precompute();
  int mx = *max_element(h.begin(), h.end());
  int l = -1, h = mx;
  bool found = false;
  while (h - l > 1 and !found) {
    mid = l + (h - l) / 2;
    if (cost(mid) < cost(mid + 1)) {
      h = mid;
    } else {
      l = mid;
    }
    if (cost(mid) == cost(mid + 1)) found = true;
  }
  cout << cost(l + 1) << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int cases = 1;
  while (cases--) {
    solvecase();
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline string bin(T n, int pos = 62) {
  string s;
  T i, one = 1, two = 2;
  for (i = (one << (pos - 1)); i > 0; i = (i >> 1)) s += ((n & i) ? "1" : "0");
  return s;
}
int lsb(unsigned int v) {
  int r;
  static const int MultiplyDeBruijnBitPosition[32] = {
      0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9};
  r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
  return r + 1;
}
template <class T>
inline int msb(T n) {
  return (n == 0) ? 0 : (1 + msb(n >> 1));
}
template <class T>
inline T getbit(T n, int pos) {
  return ((n & (1 << pos)) ? 1 : 0);
}
template <class T>
inline int countbit(T n) {
  return (n == 0) ? 0 : (1 + countbit(n & (n - 1)));
}
template <class T>
inline void setbit(T &n, int p) {
  n = n | (1LL << p);
}
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
bool isequal(vector<int> a, vector<int> b) {
  for (int i = 0; i < (a.size()); i++)
    if (a[i] != b[i]) return false;
  return true;
}
template <class T>
bool allequal(vector<T> a) {
  sort(a.begin(), a.end());
  return a[0] == a[a.size() - 1];
}
template <class T1, class T2>
void printpairs(vector<pair<T1, T2>> p) {
  for (auto t : p) {
    cout << "(" << t.first << " " << t.second << ")  ";
  }
  cout << endl;
}
template <class T>
void printvec(vector<T> a) {
  for (int i = 0; i < (a.size()); i++) cout << a[i] << " ";
  cout << endl;
}
void printarray(int *a, int n) {
  for (int i = 0; i < (n); i++) cout << *(a + i) << " ";
  cout << endl;
}
template <typename T>
void printmatrix(vector<vector<T>> a, int n, int m, int width = 5) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << setw(width) << a[i][j];
    }
    cout << endl;
  }
}
template <typename T>
void readmatrix(vector<vector<T>> &a, int n, int m) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
}
template <class T>
void printsubarray(vector<T> a, int start, int end) {
  if (start < 0 or end > a.size() - 1) cout << "Out of bounds" << endl;
  for (int i = start; i <= end; i++) cout << a[i] << " ";
  cout << endl;
}
bool isprime(int n) {
  if (n < 2) return false;
  if (n == 2) return true;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void split(const string &s, char c, vector<string> &result) {
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) result.push_back(x);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << ' ';
  err(++it, args...);
}
void yup() { cout << "Yes" << endl; }
void nope() { cout << "No" << endl; }
void Yup() { cout << "YES" << endl; }
void Nope() { cout << "NO" << endl; }
template <typename T>
void readvec(vector<T> &a, int size) {
  T tmp;
  a.clear();
  for (int i = 0; i < (size); i++) {
    cin >> tmp;
    a.push_back(tmp);
  }
}
int n, a, r, m;
vector<int> h;
vector<long long> prefix;
vector<long long> postfix;
void precompute() {
  prefix = vector<long long>(n + 2, 0LL);
  postfix = vector<long long>(n + 2, 0LL);
  for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + (long long)h[i - 1];
  }
  for (int i = n; i > 0; i--) {
    postfix[i] = postfix[i + 1] + (long long)h[i - 1];
  }
}
long long cost(int f) {
  long long cur = 0;
  int idx = lower_bound(h.begin(), h.end(), f) - h.begin();
  long long need = ((long long)idx * (long long)f) - prefix[idx];
  long long have = postfix[idx + 1] - ((long long)(n - idx) * (long long)f);
  if (a + r > m) {
    if (have >= need) {
      cur = m * need + (have - need) * r;
    } else {
      cur = m * have + (need - have) * a;
    }
  } else {
    cur = have * r + need * a;
  }
  return cur;
}
void solvecase() {
  int mid;
  cin >> n >> a >> r >> m;
  readvec(h, n);
  sort(h.begin(), h.end());
  precompute();
  int mx = *max_element(h.begin(), h.end());
  int l = -1, h = mx;
  bool found = false;
  while (h - l > 1 and !found) {
    mid = l + (h - l) / 2;
    if (cost(mid) < cost(mid + 1)) {
      h = mid;
    } else {
      l = mid;
    }
    if (cost(mid) == cost(mid + 1)) found = true;
  }
  cout << cost(l + 1) << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int cases = 1;
  while (cases--) {
    solvecase();
  }
  return 0;
}

```