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.io.*;
public class Main 
{
 
	static ArrayList<Integer> adj[];
	static char color[];
	static boolean b[],visited[],possible;
	static int level[];
	static Map<Integer,HashSet<Integer>> s;
	static int totalnodes,colored;
	static int count[];
	static long sum[];
	static int nodes;
	static double ans=0;
	static long[] as=new long[10001];
	static long c1=0,c2=0;
	static long[] a,d;
	static int max=100000000;
	public static void main(String[] args) throws IOException
	{
		in=new InputReader(System.in);
		w=new PrintWriter(System.out);
        int n=in.nextInt(),p=in.nextInt(),q=in.nextInt(),r=in.nextInt();
        a=new long[n];
        nextIntArray(n);
       long[] p1=new long[n];
       long[] q1=new long[n];
       long[] r1=new long[n];
       p1=Arrays.copyOf(a,n);
       q1=Arrays.copyOf(a,n);
       r1=Arrays.copyOf(a,n);
       for(int i=0;i<n;i++)
    	   p1[i]*=p;
       for(int i=0;i<n;i++)
    	   q1[i]*=q;
       for(int i=0;i<n;i++)
    	   r1[i]*=r;
       for(int i=1;i<n;i++)
    	   p1[i]=Math.max(p1[i],p1[i-1]);
       for(int i=n-2;i>=0;i--)
    	   r1[i]=Math.max(r1[i],r1[i+1]);
      long max=Long.MIN_VALUE;
       for(int i=0;i<n;i++)
    	   if(p1[i]+q1[i]+r1[i]>max)
    		   max=p1[i]+q1[i]+r1[i];
       w.print(max);
       
        w.close();
}
	


	private static void nextIntArray(int n) {
		 for(int i=0;i<n;i++)
			 a[i]=in.nextInt();
		
	}



	
  public static void bfs()
  {
	 level[1]=1;
	 visited[1]=true;
	 Queue<Integer> q=new LinkedList<Integer>();
	 q.add(1);
	 while(!q.isEmpty())
	 {
		 int t=q.poll();
		 for(int i=0;i<adj[t].size();i++)
		 {
			 if(!visited[adj[t].get(i)])
			 {
				 level[adj[t].get(i)]=level[t]+1;
				 visited[adj[t].get(i)]=true;
				 q.add(adj[t].get(i));
			 }
		 }
	 }
  }
  public static void dfs(int i)
  {
	  visited[i]=true;
	  for(int j:adj[i])
	  {
		  if(!visited[j])
			  {
			  dfs(j);
			  nodes++;
			  }
	  }
	  
  }
	public static String rev(String s)
	{
		StringBuilder sb=new StringBuilder(s);
		sb.reverse();
		return sb.toString();
	}
	static long lcm(long a, long b)
	{
	    return a * (b / gcd(a, b));
	}
	static long gcd(long a, long b)
	{
	    while (b > 0)
	    {
	        long temp = b;
	        b = a % b; // % is remainder
	        a = temp;
	    }
	    return a;
	}
	static InputReader in;
	static PrintWriter w;
static class InputReader 
{
 
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
private SpaceCharFilter filter;
 
public InputReader(InputStream stream)
{
  this.stream = stream;
}
 
public int snext()
{
  if (snumChars == -1)
    throw new InputMismatchException();
  if (curChar >= snumChars)
  {
    curChar = 0;
    try 
    {
      snumChars = stream.read(buf);
    }
    catch (IOException e)
    {
      throw new InputMismatchException();
    }
    if (snumChars <= 0)
      return -1;
  }
  return buf[curChar++];
}
 
public int nextInt() 
{
  int c = snext();
  while (isSpaceChar(c)) 
  {
    c = snext();
  }
  int sgn = 1;
  if (c == '-')
  {
    sgn = -1;
    c = snext();
  }
  int res = 0;
  do
  {
    if (c < '0' || c > '9')
      throw new InputMismatchException();
    res *= 10;
    res += c - '0';
    c = snext();
  }
  while (!isSpaceChar(c));
  return res * sgn;
}
 
public long nextLong() 
{
  int c = snext();
  while (isSpaceChar(c)) 
  {
    c = snext();
  }
  int sgn = 1;
  if (c == '-')
  {
    sgn = -1;
    c = snext();
  }
  long res = 0;
  do
  {
    if (c < '0' || c > '9')
      throw new InputMismatchException();
    res *= 10;
    res += c - '0';
    c = snext();
  }
  while (!isSpaceChar(c));
  return res * sgn;
}
 
public static void nextIntArray(int n) 
{
	 for(int i=0;i<n;i++)
		 a[i]=in.nextInt();
}
	    
public int[] nextIntArray(int n, int off)
{
	 int[] arr = new int[n + off];
	   for (int i = 0; i < n; i++)
	   {
	    arr[i + off] = nextInt();
	    }
	    return arr;
	    }
	    
public long[] nextLongArray(int n)
{
return nextLongArray(n, 0);
	    }
        
	public long[] nextLongArray(int n, int off)
	{
	 long[] arr = new long[n + off];
	 for (int i = 0; i < n; i++)
	 {
		  arr[i + off] = nextLong();
		 }
 return arr;
	}
 
 
public String readString() 
{
  int c = snext();
  while (isSpaceChar(c)) 
  {
    c = snext();
  }
  StringBuilder res = new StringBuilder();
  do
  {
    res.appendCodePoint(c);
    c = snext();
  }
  while (!isSpaceChar(c));
  return res.toString();
}
 
public String nextLine() 
{
  int c = snext();
  while (isSpaceChar(c))
    c = snext();
  StringBuilder res = new StringBuilder();
  do
  {
    res.appendCodePoint(c);
    c = snext();
  }
  while (!isEndOfLine(c));
  return res.toString();
}
 
public boolean isSpaceChar(int c)
{
  if (filter != null)
    return filter.isSpaceChar(c);
  return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
 
private boolean isEndOfLine(int c) 
{
  return c == '\n' || c == '\r' || c == -1;
}
 
public interface SpaceCharFilter
{
  public boolean isSpaceChar(int ch);
}
}
	
}