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

public class Main {
    static BufferedReader br;
       //static  long mod  = 1000
    static HashSet<Integer> p  = new HashSet<>();
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
     //   tc = cinI();

        //  sieve();
        while (tc-- > 0) {
            int[] npqr=  readArray(4,0,1);
            long[] arr = readArray(npqr[0],0);

            long[] pqr = new long[3];
         Arrays.fill(pqr,Long.MIN_VALUE);
            //0 for p 1 for q 2 for r
          //  System.out.println(pqr[0]+ " "+pqr[1]+" "+pqr[2]);
            for(int i=0;i<npqr[0];i++){
                pqr[0]=max(pqr[0],(npqr[1]*arr[i]));
                pqr[1]=max(pqr[1],pqr[0]+(npqr[2]*arr[i]));
                pqr[2]=max(pqr[2],pqr[1]+(npqr[3]*arr[i]));
               // System.out.println(pqr[0]+ " "+pqr[1]+" "+pqr[2]);
            }
           // long sum = pqr[0]+pqr[1]+pqr[2];
            System.out.println(pqr[2]);

        }
    }

    public static void sieve(){
         int[] pf = new int[100000+1];
        //0 prime //1 not prime
        pf[0]=1;
        pf[1]=1;
        for(int j=2;j<pf.length;j++){

            if(pf[j]==0 && ((long)j*j<pf.length)){
                for(int k=j*j;k<pf.length;k+=j){
                    pf[k]=1;
                }
            }
        }
        for(int j=2;j<pf.length;j++){
          if(pf[j]==0){
              p.add(j);
          }

        }
    }






    public  static  int[] readArray(int n,int x ,int z)throws Exception{
        int[] arr= new int[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
    }
      public  static  long[] readArray(int n,int x )throws Exception{
        long[] arr= new long[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
      }

    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public  static HashSet<Integer>[]  Graph(int n,int edge,int directed)throws Exception{
        HashSet<Integer>[] tree=  new HashSet[n];

        for(int j=0;j<edge;j++){

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if(directed==0){

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
    public static String[] cinA(int x) throws Exception{
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}

class range {
    int l;
    int r;
    int diff;

    public range(int l, int r, int diff) {
        this.l = l;
        this.r = r;
        this.diff = diff;
    }
}

class sortRange implements Comparator<range> {


    @Override
    public int compare(range range, range t1) {
        if (range.diff != t1.diff)
            return t1.diff - range.diff;
        return range.l - t1.l;

    }}
class Diag{

    int c0;
    int c1;
    public Diag(int c0,int c1){
        this.c0=c0;
        this.c1=c1;
    }
}