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.
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
public static void main(String[] args)throws java.lang.Exception
{
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  PrintWriter out = new PrintWriter(System.out);

  int n,i;
  long p,q,r,ans;
  String str;
  String[] token;

  str=in.readLine().trim();
  token=str.split(" ");

  n=Integer.parseInt(token[0]);
  p=Long.parseLong(token[1]);
  q=Long.parseLong(token[2]);
  r=Long.parseLong(token[3]);

  int[] a=new int[n];
  long[] parr=new long[n];
  long[] qarr=new long[n];
  long[] rarr=new long[n];

  str=in.readLine().trim();
  token=str.split(" ");

  for(i=0;i<n;i++)
  {
    a[i]=Integer.parseInt(token[i]);

    parr[i]=p*a[i];
    qarr[i]=q*a[i];
    rarr[i]=r*a[i];
  }

  qarr[n-1]+=rarr[n-1];

  for(i=n-1;i>=1;i--)
  {
    rarr[i-1]=Math.max(rarr[i], rarr[i-1]);
    qarr[i-1]+=rarr[i-1];
  }

  parr[n-1]+=qarr[n-1];

  for(i=n-1;i>=1;i--)
  {
    qarr[i-1]=Math.max(qarr[i], qarr[i-1]);
    parr[i-1]+=qarr[i-1];
  }

  ans=parr[n-1];

  for(i=n-2;i>=0;i--)
  {
    ans=Math.max(ans, parr[i]);
  }

  out.println(ans);


  out.flush();
  out.close();
}    
} 