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 static java.util.Collections.*;
import static java.lang.Math.*;

@SuppressWarnings("unchecked")
public class B_Marvolo_Gaunt_s_Ring {
    public static PrintWriter out;
    public static InputReader in;
    public static long arr[];
    public static void main(String[] args)throws IOException {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);
        
        long p,q,r; int n; n = in.nextInt();
        arr = new long[n];
        p = in.nextLong(); q = in.nextLong(); r = in.nextLong();
        for(int i=0;i<n;i++) arr[i] = in.nextLong();
        long ans = Long.MIN_VALUE;
        int mnf[] = new int[n];
        int mnb[] = new int[n];
        int mxf[] = new int[n];
        int mxb[] = new int[n];
        int max = 0; int min = 0;
        for(int i=0;i<n;i++){
            if(arr[i]>arr[max]){
                max = i;
            }
            if(arr[i]<arr[min]){
                min = i;
            }
            mnf[i] = min; mxf[i] = max;
        }
        max = n-1; min = n-1;
        for(int i=n-1;i>=0;i--){
            if(arr[i]>arr[max]){
                max = i;
            }
            if(arr[i]<arr[min]){
                min = i;
            }
            mnb[i] = min; mxb[i] = max;
        }
        for(int i=0;i<n;i++){
            long val = q*arr[i];
            if(p<0)
                val+=(p*arr[mnf[i]]);
            else
                val+=(p*arr[mxf[i]]);
            if(r<0)
                val+=(r*arr[mnb[i]]);
            else
                val+=(r*arr[mxb[i]]);
            ans = max(ans,val);
        }
        out.println(ans);
        out.close();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

}