#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct Fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,
                                            vector<vector<long long>> b) {
    vector<vector<long long>> c(a.size(), vector<long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++)
      for (int q = 0; q < b[0].size(); q++) {
        long long num = 0;
        for (int e = 0; e < a[0].size(); i++) num += a[i][e] * b[e][q];
        c[i][q] = num;
      }
    return c;
  }
};
struct Euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int maxnD = 100000 + 5;
const long long INFD = 0x3f3f3f3f;
;
struct Dijkstra {
  struct Edge {
    int from, to;
    long long dist;
  };
  struct HeapNode {
    long long d;
    int u;
    bool operator<(const HeapNode &rhs) const { return d > rhs.d; }
  };
  vector<Edge> edges;
  vector<int> G[maxnD];
  bool done[maxnD];
  long long d[maxnD];
  int p[maxnD], n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, long long dist) {
    edges.push_back((Edge){from, to, dist});
    int m = edges.size();
    G[from].push_back(m - 1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> q;
    memset(d, INFD, sizeof(d));
    d[s] = 0;
    memset(done, 0, sizeof(done));
    q.push((HeapNode){0, s});
    while (!q.empty()) {
      HeapNode x = q.top();
      q.pop();
      int u = x.u;
      if (done[u]) continue;
      done[u] = true;
      for (int i = 0; i < G[u].size(); i++) {
        Edge &e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
const int maxnL = 500000 + 5;
const int INFL = 0x3f3f3f3f;
struct LIS {
  int g[maxnL], a[maxnL], d[maxnL];
  void lis(int n) {
    for (int i = 1; i <= n; i++) g[i] = INFL;
    for (int i = 1; i < n; i++) {
      int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
      g[k] = a[i];
    }
  }
};
const int maxnS = 200000 + 5;
struct SegmentTree {
  int a[maxnS];
  int sumv[maxnS * 4], minv[maxnS * 4], maxv[maxnS * 4], addv[maxnS * 4],
      setv[maxnS * 4];
  int lc, rc, v;
  int _min, _max, _sum;
  void build(int l, int r, int o) {
    if (l == r) return void(sumv[o] = minv[o] = maxv[o] = a[l]);
    build(l, (l + r) >> 1, o << 1);
    build(((l + r) >> 1) + 1, r, o << 1 | 1);
  }
  void maintain(int l, int r, int o) {
    sumv[o] = minv[o] = maxv[o] = a[l];
    if (r > l) {
      sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
      minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
      maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
    }
    minv[o] += addv[o], maxv[o] += addv[o], sumv[o] += addv[o] * (r - l + 1);
  }
  void update(int l, int r, int o) {
    if (l >= lc && r <= rc)
      addv[o] += v;
    else {
      int m = (l + r) >> 1;
      if (lc <= m) update(l, (l + r) >> 1, o << 1);
      if (rc > m) update(((l + r) >> 1) + 1, r, o << 1 | 1);
    }
    maintain(l, r, o);
  }
  void query(int l, int r, int o, int add) {
    if (lc <= l && r <= rc) {
      _sum += sumv[o] + add * (r - l + 1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {
      int m = (l + r) >> 1;
      if (lc <= m) query(l, m, o << 1, add + addv[o]);
      if (rc > m) query(m + 1, r, o << 1 | 1, add + addv[o]);
    }
  }
};
const int maxnB = 100000 + 5;
struct BIT {
  int c[maxnB], n;
  int lowbit(int x) { return x & -x; }
  int sum(int x) {
    int ret = 0;
    while (x > 0) {
      ret += c[x];
      x -= lowbit(x);
    }
    return ret;
  }
  void add(int x, int d) {
    while (x <= n) {
      c[x] += d;
      x += lowbit(x);
    }
  }
};
const int maxnEC = 200000 + 5;
struct EXCRT {
  long long ai[maxnEC], bi[maxnEC], n;
  inline long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    long long gcd = exgcd(b, a % b, x, y);
    long long t = x;
    x = y, y = t - (a / b) * y;
    return gcd;
  }
  inline long long mul(long long a, long long b, long long mod) {
    long long s = 0;
    while (b) {
      if (b & 1) s = (s + a) % mod;
      a = (a + a) % mod;
      b >>= 1;
    }
    return s % mod;
  }
  long long excrt() {
    long long x = 0, y = 0, k;
    long long M = bi[1], ans = ai[1];
    for (int i = 2; i <= 2; i++) {
      long long a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
      long long gcd = exgcd(a, b, x, y), bg = b / gcd;
      if (c % gcd != 0) return -1;
      x = mul(x, c / gcd, bg);
      ans += x * M;
      M *= bg;
      ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
long long b[maxn], n, a, r, m;
long long getnum(long long d) {
  long long sum1 = 0, sum2 = 0;
  for (long long i = 0; i < n; i++)
    b[i] < d ? sum1 += d - b[i] : sum2 += b[i] - d;
  if (m >= a + r) return a * sum1 + r * sum2;
  long long num = min(sum1, sum2);
  return a * (sum1 - num) + r * (sum2 - num) + m * num;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a >> r >> m;
  for (long long i = 0; i < n; i++) cin >> b[i];
  sort(b, b + n);
  long long ans = 1LL << 60;
  long long l = 0, r = 1000000000;
  while (l <= r) {
    long long m = (l + r) >> 1, mon, rm = 1LL << 60;
    mon = getnum(m);
    rm = getnum(m + 1);
    ans = min(mon, rm);
    if (rm < mon)
      l = m + 1;
    else
      r = m - 1;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate a CPP solution 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;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct Fast_power {
  long long integer(long long n, long long e,
                    long long my_mod = 9223372036854775807LL) {
    long long ans = 1;
    while (e) {
      if (e & 1)
        ans = (ans * n) % my_mod, e--;
      else
        n = (n * n) % my_mod, e >>= 1;
    }
    return ans;
  }
  vector<vector<long long>> matrix_multiply(vector<vector<long long>> a,
                                            vector<vector<long long>> b) {
    vector<vector<long long>> c(a.size(), vector<long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); i++)
      for (int q = 0; q < b[0].size(); q++) {
        long long num = 0;
        for (int e = 0; e < a[0].size(); i++) num += a[i][e] * b[e][q];
        c[i][q] = num;
      }
    return c;
  }
};
struct Euclidean {
  int gcdi(int a, int b) { return b ? gcdi(b, a % b) : a; }
  double gcdf(double a, double b, double accuracy) {
    return b <= accuracy ? a : gcdf(b, fmod(a, b), accuracy);
  }
};
const int maxnD = 100000 + 5;
const long long INFD = 0x3f3f3f3f;
;
struct Dijkstra {
  struct Edge {
    int from, to;
    long long dist;
  };
  struct HeapNode {
    long long d;
    int u;
    bool operator<(const HeapNode &rhs) const { return d > rhs.d; }
  };
  vector<Edge> edges;
  vector<int> G[maxnD];
  bool done[maxnD];
  long long d[maxnD];
  int p[maxnD], n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, long long dist) {
    edges.push_back((Edge){from, to, dist});
    int m = edges.size();
    G[from].push_back(m - 1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> q;
    memset(d, INFD, sizeof(d));
    d[s] = 0;
    memset(done, 0, sizeof(done));
    q.push((HeapNode){0, s});
    while (!q.empty()) {
      HeapNode x = q.top();
      q.pop();
      int u = x.u;
      if (done[u]) continue;
      done[u] = true;
      for (int i = 0; i < G[u].size(); i++) {
        Edge &e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
const int maxnL = 500000 + 5;
const int INFL = 0x3f3f3f3f;
struct LIS {
  int g[maxnL], a[maxnL], d[maxnL];
  void lis(int n) {
    for (int i = 1; i <= n; i++) g[i] = INFL;
    for (int i = 1; i < n; i++) {
      int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
      g[k] = a[i];
    }
  }
};
const int maxnS = 200000 + 5;
struct SegmentTree {
  int a[maxnS];
  int sumv[maxnS * 4], minv[maxnS * 4], maxv[maxnS * 4], addv[maxnS * 4],
      setv[maxnS * 4];
  int lc, rc, v;
  int _min, _max, _sum;
  void build(int l, int r, int o) {
    if (l == r) return void(sumv[o] = minv[o] = maxv[o] = a[l]);
    build(l, (l + r) >> 1, o << 1);
    build(((l + r) >> 1) + 1, r, o << 1 | 1);
  }
  void maintain(int l, int r, int o) {
    sumv[o] = minv[o] = maxv[o] = a[l];
    if (r > l) {
      sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
      minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
      maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
    }
    minv[o] += addv[o], maxv[o] += addv[o], sumv[o] += addv[o] * (r - l + 1);
  }
  void update(int l, int r, int o) {
    if (l >= lc && r <= rc)
      addv[o] += v;
    else {
      int m = (l + r) >> 1;
      if (lc <= m) update(l, (l + r) >> 1, o << 1);
      if (rc > m) update(((l + r) >> 1) + 1, r, o << 1 | 1);
    }
    maintain(l, r, o);
  }
  void query(int l, int r, int o, int add) {
    if (lc <= l && r <= rc) {
      _sum += sumv[o] + add * (r - l + 1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {
      int m = (l + r) >> 1;
      if (lc <= m) query(l, m, o << 1, add + addv[o]);
      if (rc > m) query(m + 1, r, o << 1 | 1, add + addv[o]);
    }
  }
};
const int maxnB = 100000 + 5;
struct BIT {
  int c[maxnB], n;
  int lowbit(int x) { return x & -x; }
  int sum(int x) {
    int ret = 0;
    while (x > 0) {
      ret += c[x];
      x -= lowbit(x);
    }
    return ret;
  }
  void add(int x, int d) {
    while (x <= n) {
      c[x] += d;
      x += lowbit(x);
    }
  }
};
const int maxnEC = 200000 + 5;
struct EXCRT {
  long long ai[maxnEC], bi[maxnEC], n;
  inline long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    long long gcd = exgcd(b, a % b, x, y);
    long long t = x;
    x = y, y = t - (a / b) * y;
    return gcd;
  }
  inline long long mul(long long a, long long b, long long mod) {
    long long s = 0;
    while (b) {
      if (b & 1) s = (s + a) % mod;
      a = (a + a) % mod;
      b >>= 1;
    }
    return s % mod;
  }
  long long excrt() {
    long long x = 0, y = 0, k;
    long long M = bi[1], ans = ai[1];
    for (int i = 2; i <= 2; i++) {
      long long a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
      long long gcd = exgcd(a, b, x, y), bg = b / gcd;
      if (c % gcd != 0) return -1;
      x = mul(x, c / gcd, bg);
      ans += x * M;
      M *= bg;
      ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
  }
};
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 5;
long long b[maxn], n, a, r, m;
long long getnum(long long d) {
  long long sum1 = 0, sum2 = 0;
  for (long long i = 0; i < n; i++)
    b[i] < d ? sum1 += d - b[i] : sum2 += b[i] - d;
  if (m >= a + r) return a * sum1 + r * sum2;
  long long num = min(sum1, sum2);
  return a * (sum1 - num) + r * (sum2 - num) + m * num;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a >> r >> m;
  for (long long i = 0; i < n; i++) cin >> b[i];
  sort(b, b + n);
  long long ans = 1LL << 60;
  long long l = 0, r = 1000000000;
  while (l <= r) {
    long long m = (l + r) >> 1, mon, rm = 1LL << 60;
    mon = getnum(m);
    rm = getnum(m + 1);
    ans = min(mon, rm);
    if (rm < mon)
      l = m + 1;
    else
      r = m - 1;
  }
  cout << ans << endl;
  return 0;
}

```