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;
long long GCD(long long a, long long b) {
  long long maxi = max(a, b);
  long long mini = min(a, b);
  while (maxi && mini) {
    long long t = mini;
    mini = maxi % mini;
    maxi = t;
  }
  return max(maxi, mini);
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) {
      res = (res * x);
    }
    x = (x * x);
    y = y >> 1;
  }
  return res;
}
long long ncr(long long x, long long y) {
  long long ans = 1;
  y = (y > x - y ? x - y : y);
  for (long long i = 0; i < y; i++) {
    ans = (ans * (x - i)) % 1000000007;
    ans = (ans * power(i + 1, 1000000007 - 2)) % 1000000007;
    ans = ans % 1000000007;
  }
  return ans;
}
map<pair<int, int>, long long> dp;
long long max_value(int i, int j, long long vals[], long long arr[], int n) {
  if (j == 3) {
    return 0;
  }
  if (i == n) {
    return -5000000000000000000;
  }
  if (dp.find({i, j}) != dp.end()) {
    return dp[{i, j}];
  }
  long long maxi = -5000000000000000000;
  long long a = max_value(i + 1, j, vals, arr, n);
  maxi = max(maxi, a);
  if (j <= 2) {
    long long b = arr[i] * vals[j] + max_value(i + 1, j + 1, vals, arr, n);
    maxi = max(maxi, b);
  }
  if (j <= 1) {
    long long b = arr[i] * (vals[j] + vals[j + 1]) +
                  max_value(i + 1, j + 2, vals, arr, n);
    maxi = max(maxi, b);
  }
  if (j == 0) {
    long long b = arr[i] * (vals[j] + vals[j + 1] + vals[j + 2]) +
                  max_value(i + 1, j + 3, vals, arr, n);
    maxi = max(maxi, b);
  }
  return dp[{i, j}] = maxi;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, p, q, r;
  cin >> n >> p >> q >> r;
  long long arr[n];
  long long vals[] = {p, q, r};
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  long long ans = max_value(0, 0, vals, arr, n);
  cout << ans << "\n";
  return 0;
}
