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.*;

public class Main
{
    public static void main(String args[])throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BigInteger max= new BigInteger("0");
        StringTokenizer str1=new StringTokenizer(br.readLine());
        int N=Integer.parseInt(str1.nextToken());
        int p=Integer.parseInt(str1.nextToken());
        int q=Integer.parseInt(str1.nextToken());
        int r=Integer.parseInt(str1.nextToken());
        int ar[]=new int[N];
        long maxLeft[]=new long[N];
        long maxRight[]=new long[N];
        StringTokenizer str2=new StringTokenizer(br.readLine());
        for(int x=0;x<N;x++)
        {
            ar[x]=Integer.parseInt(str2.nextToken());
            if(x==0)
                maxLeft[x]=ar[x]*(long)p;
            else if(x>=1)
            {
                maxLeft[x]=maxLeft[x-1];
                long val=ar[x]*(long)p;
                if(maxLeft[x]<val)maxLeft[x]=val;
            }
        }
        maxRight[N-1]=ar[N-1]*(long)r;
        for(int x=N-2;x>=0;x--)
        {
            maxRight[x]=maxRight[x+1];
            long val=ar[x]*(long)r;
            if(val>maxRight[x])maxRight[x]=val;
        }
        max=BigInteger.valueOf(maxRight[0]).add(BigInteger.valueOf(maxLeft[0])).add(BigInteger.valueOf(ar[0]*(long)q));
        for(int x=0;x<N;x++)
        {
            BigInteger val=BigInteger.valueOf(maxRight[x]).add(BigInteger.valueOf(maxLeft[x])).add(BigInteger.valueOf(ar[x]*(long)q));
            if(val.compareTo(max)>0)max=val;
            //System.out.println(max+" "+ar[x]*(long)q);
        }
        System.out.println(max);
    }
}