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 a[100005];
long long maxzuo[100005];
long long maxyou[100005];
long long minzuo[100005];
long long minyou[100005];
int main() {
  long long n, p, q, r;
  cin >> n >> p >> q >> r;
  for (int i = 1; i <= n; i++) cin >> a[i];
  long long maxx = a[1];
  long long minn = a[1];
  for (int i = 1; i <= n; i++) {
    maxx = max(maxx, a[i]);
    minn = min(minn, a[i]);
  }
  if (n == 1) {
    cout << a[1] * (p + q + r);
    return 0;
  }
  maxzuo[1] = a[1];
  minzuo[1] = a[1];
  for (int i = 2; i <= n; i++) {
    maxzuo[i] = max(maxzuo[i - 1], a[i]);
    minzuo[i] = min(minzuo[i - 1], a[i]);
  }
  maxyou[n] = a[n];
  minyou[n] = a[n];
  for (int i = n - 1; i >= 1; i--) {
    maxyou[i] = max(maxyou[i + 1], a[i]);
    minyou[i] = min(minyou[i + 1], a[i]);
  }
  if (p >= 0 && q >= 0 && r >= 0) {
    cout << maxx * (p + q + r);
  } else if (p <= 0 && q <= 0 && r <= 0) {
    cout << minn * (p + q + r);
  } else if (p >= 0 && q >= 0 && r <= 0) {
    long long haha = maxzuo[n] * (p + q) + minyou[n] * r;
    for (int i = 1; i <= n - 1; i++) {
      haha = max(haha, maxzuo[i] * (p + q) + minyou[i + 1] * r);
    }
    cout << haha << endl;
  } else if (p >= 0 && q <= 0 && r <= 0) {
    long long haha = maxzuo[1] * (p) + minyou[1] * (r + q);
    for (int i = 2; i <= n; i++) {
      haha = max(haha, maxzuo[i - 1] * p + minyou[i] * (q + r));
    }
    cout << haha << endl;
  } else if (p <= 0 && q <= 0 && r >= 0) {
    long long haha = minzuo[n] * (p + q) + maxyou[n] * r;
    for (int i = 1; i <= n - 1; i++) {
      haha = max(haha, minzuo[i] * (p + q) + maxyou[i + 1] * r);
    }
    cout << haha << endl;
  } else if (p <= 0 && q >= 0 && r >= 0) {
    long long haha = minzuo[1] * (p) + maxyou[1] * (r + q);
    for (int i = 2; i <= n; i++) {
      haha = max(haha, minzuo[i - 1] * p + maxyou[i] * (q + r));
    }
    cout << haha << endl;
  } else if (p <= 0 && q >= 0 && r <= 0) {
    long long haha = a[1] * (p + q) + minyou[2] * r;
    haha = max(haha, minzuo[n - 1] * p + a[n] * (q + r));
    haha = max(haha, a[1] * (p + q + r));
    haha = max(haha, a[n] * (p + q + r));
    for (int i = 2; i <= n - 1; i++) {
      haha = max(haha, minzuo[i - 1] * p + a[i] * q + minyou[i + 1] * r);
    }
    cout << haha << endl;
  } else if (p >= 0 && q <= 0 && r >= 0) {
    long long haha = a[1] * (p + q) + maxyou[2] * r;
    haha = max(haha, maxzuo[n - 1] * p + a[n] * (q + r));
    haha = max(haha, a[1] * (p + q + r));
    haha = max(haha, a[n] * (p + q + r));
    for (int i = 2; i <= n - 1; i++) {
      haha = max(haha, maxzuo[i - 1] * p + a[i] * q + maxyou[i + 1] * r);
    }
    cout << haha << endl;
  }
  return 0;
}
