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;
struct node {
  long long mi;
  long long mx;
};
node tree[1000005];
long long a[1000005];
void build(long long low, long long high, long long pos) {
  if (low == high) {
    tree[pos].mx = a[low];
    tree[pos].mi = a[low];
    return;
  }
  long long mid = (high + low) / 2;
  build(low, mid, 2 * pos);
  build(mid + 1, high, 2 * pos + 1);
  tree[pos].mi = min(tree[2 * pos + 1].mi, tree[2 * pos].mi);
  tree[pos].mx = max(tree[2 * pos + 1].mx, tree[2 * pos].mx);
}
long long query(long long low, long long high, long long pos, long long ql,
                long long qh, bool f) {
  if (ql <= low && qh >= high) {
    if (f) {
      return tree[pos].mi;
    } else {
      return tree[pos].mx;
    }
  } else if (high < ql || qh < low) {
    if (f) {
      return 3e18;
    } else {
      return -3e18;
    }
  }
  long long mid = (high + low) / 2;
  if (f) {
    return min(query(low, mid, 2 * pos, ql, qh, f),
               query(mid + 1, high, 2 * pos + 1, ql, qh, f));
  } else {
    return max(query(low, mid, 2 * pos, ql, qh, f),
               query(mid + 1, high, 2 * pos + 1, ql, qh, f));
  }
}
int main() {
  long long p, q, i, r, n;
  cin >> n >> p >> q >> r;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, n, 1);
  long long ans = -3e18;
  for (i = 1; i <= n; i++) {
    long long x, z, y = a[i];
    if (p > 0) {
      x = query(1, n, 1, 1, i, 0);
    } else {
      x = query(1, n, 1, 1, i, 1);
    }
    if (r > 0) {
      z = query(1, n, 1, i, n, 0);
    } else {
      z = query(1, n, 1, i, n, 1);
    }
    ans = max(ans, x * p + y * q + r * z);
  }
  cout << ans << endl;
}
