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;
const int mod = 1e9 + 7;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long expo(long long base, long long pow) {
  long long ans = 1;
  while (pow != 0) {
    if (pow & 1 == 1) {
      ans = ans * base;
      ans = ans % mod;
    }
    base *= base;
    base %= mod;
    pow /= 2;
  }
  return ans;
}
long long inv(long long x) { return expo(x, mod - 2); }
unsigned long long llrand() {
  unsigned long long r = 0;
  for (int i = 0; i < 5; ++i) {
    r = (r << 15) | (rand() & 0x7FFF);
  }
  return r & 0xFFFFFFFFFFFFFFFFULL;
}
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int M = 100011;
long long arr[M], prr[M], qrr[M], rrr[M], newq[M];
int main() {
  long long p, q, r;
  int n;
  cin >> n >> p >> q >> r;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &(arr[i]));
    prr[i] = p * arr[i];
    qrr[i] = q * arr[i];
    rrr[i] = r * arr[i];
  }
  long long maxP = -0x3f3f3f3f3f3f3f3fLL;
  for (int i = 1; i <= n; i++) {
    maxP = max(maxP, prr[i]);
    newq[i] = qrr[i] + maxP;
  }
  long long ans = -0x3f3f3f3f3f3f3f3fLL;
  long long maxQ = -0x3f3f3f3f3f3f3f3fLL;
  for (int i = 1; i <= n; i++) {
    maxQ = max(maxQ, newq[i]);
    ans = max(ans, maxQ + rrr[i]);
  }
  cout << ans;
}
