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.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class manthan_b
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	
	static void shuffle(long[] a)
	{
		for(int i=0;i<a.length;i++)
		{
			int next=rnd.nextInt(a.length);

			long temp=a[i];a[i]=a[next];a[next]=temp;
		}
	}
	
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt();long p=sc.nextLong(),q=sc.nextLong(),r=sc.nextLong();
		
		long[] a=new long[n+1];long[] arr=new long[]{p,q,r};
		
		for(int i=1;i<=n;i++)
		{
			a[i]=sc.nextLong();
		}
		
		long[][] dp=new long[3][n+1];dp[0][0]=Long.MIN_VALUE;
		
		for(int i=1;i<=n;i++)
		{
			dp[0][i]=(a[i]*arr[0]);
			
			dp[0][i]=Math.max(dp[0][i],dp[0][i-1]);
		}
		
		for(int i=1;i<3;i++)
		{
			dp[i][0]=Long.MIN_VALUE;
			
			for(int j=1;j<=n;j++)
			{
				dp[i][j]=dp[i-1][j]+(arr[i]*a[j]);
					
				dp[i][j]=Math.max(dp[i][j],dp[i][j-1]);
			}
		}
		
		long res=Long.MIN_VALUE;
		
		for(int i=1;i<=n;i++)
		{
			res=Math.max(res,dp[2][i]);
		}
		
		out.println(res);out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}