Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made. 

Value of x is calculated as maximum of p·ai + q·aj + r·ak for given p, q, r and array a1, a2, ... an such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.

Input

First line of input contains 4 integers n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Next line of input contains n space separated integers a1, a2, ... an ( - 109 ≤ ai ≤ 109).

Output

Output a single integer the maximum value of p·ai + q·aj + r·ak that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

Examples

Input

5 1 2 3
1 2 3 4 5


Output

30


Input

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


Output

12

Note

In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ss = stringstream;
using ul = unsigned long long;
template <typename T>
inline T LCM(T a, T b) {
  return (a * b) / GCD(a, b);
}
template <typename T>
inline T GCD(T a, T b) {
  ll t;
  while (a) {
    t = a;
    a = b % a;
    b = t;
  }
  return b;
}
template <typename T>
inline T _max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <typename T>
inline T _min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <typename T>
inline string toString(T a) {
  return to_string(a);
}
template <typename T>
inline void toInt(string s, T &x) {
  ss str(s);
  str >> x;
}
inline void lower(string &s) {
  for (__typeof((s).begin()) it = (s).begin(); it != (s).end(); ++it)
    *it = tolower(*it);
}
inline void upper(string &s) {
  for (__typeof((s).begin()) it = (s).begin(); it != (s).end(); ++it)
    *it = toupper(*it);
}
const ll inf = 5 * (1e18);
bool palin(string s) {
  string s1 = s;
  reverse(s.begin(), s.end());
  return (s == s1);
}
ll triangle(ll n) { return (n * (n + 1)) / 2; }
bool check(ll n) {
  if (n == 1) return 0;
  if (n == 2 or n == 3) return 1;
  if (n % 2 == 0 or n % 3 == 0) return 0;
  for (ll i = 5; i * i <= n; i += 6)
    if (n % i == 0 or n % (i + 2) == 0) return 0;
  return 1;
}
ll a[100005], b[100005], c[100005];
ll tree1[4 * 100005], tree2[4 * 100005];
void make(int l, int r, int pos) {
  if (l == r) {
    tree1[pos] = a[l];
    tree2[pos] = c[l];
    return;
  }
  int mid = (l + r) / 2;
  make(l, mid, 2 * pos + 1);
  make(mid + 1, r, 2 * pos + 2);
  tree1[pos] = max(tree1[2 * pos + 1], tree1[2 * pos + 2]);
  tree2[pos] = max(tree2[2 * pos + 1], tree2[2 * pos + 2]);
}
ll query1(int low, int high, int l, int r, int pos) {
  if (high < l or r < low) {
    return -inf;
  }
  if (l <= low and r >= high) {
    return tree1[pos];
  }
  int mid = (low + high) / 2;
  return max(query1(low, mid, l, r, 2 * pos + 1),
             query1(mid + 1, high, l, r, 2 * pos + 2));
}
ll query2(int low, int high, int l, int r, int pos) {
  if (high < l or r < low) {
    return -inf;
  }
  if (l <= low and r >= high) {
    return tree2[pos];
  }
  int mid = (low + high) / 2;
  return max(query2(low, mid, l, r, 2 * pos + 1),
             query2(mid + 1, high, l, r, 2 * pos + 2));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int n;
  ll p, q, r;
  cin >> n >> p >> q >> r;
  vector<ll> v1;
  for (int i = 0; i < 4 * n; i++) {
    tree1[i] = -inf;
    tree2[i] = -inf;
  }
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    v1.push_back(x);
  }
  for (int i = 0; i < n; i++) {
    a[i] = p * v1[i];
    b[i] = q * v1[i];
    c[i] = r * v1[i];
  }
  make(0, n - 1, 0);
  ll ans = -inf;
  for (int i = 0; i < n; i++) {
    ll u = query1(0, n - 1, 0, i, 0);
    ll v = query2(0, n - 1, i, n - 1, 0);
    ll d = u + v + b[i];
    ans = max(ans, d);
  }
  cout << ans;
  cout << "\n";
  return 0;
}
