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 static java.lang.Double.parseDouble;
import static java.lang.Double.valueOf;
import static java.lang.Long.max;
import static java.lang.Long.min;
import static java.lang.Integer.max;
import static java.lang.Integer.min;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.StrictMath.abs;
import static java.lang.System.err;
import static java.lang.System.exit;
import static java.util.Arrays.sort;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;


public class A {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
    static int n;
    static int p,q,r,a[];
    static long dp[][];
    static final Long mn = -3000000000000000000L;

    static long fun(int i,int type) {
        if(type==3) return 0;
        if(i==n) return mn;
        if(dp[type][i] != mn-1) return dp[type][i];
        long ans = mn;
        ans = max(ans,fun(i+1,type));
        if(type == 0) ans = max(ans, a[i] * 1L * p  + fun(i,1));
        else if(type == 1) ans = max(ans, a[i] * 1L * q + fun(i,2));
        else if(type == 2) ans = max(ans, a[i] * 1L * r + fun(i,3));
        return dp[type][i] = ans;
    }

    static void solve() throws Exception {
        n = nextInt();
        p = nextInt(); q = nextInt(); r = nextInt();
        a = new int[n];
        for(int i=0;i<n;i++) a[i] = nextInt();
        dp = new long[5][n];
        for(int j=0;j<5;j++) for(int i=0;i<n;i++) dp[j][i] = mn -1;
        out.print(fun(0,0));
    }


    public static int[] convertIntegers(List<Integer> integers) {
        int[] ret = new int[integers.size()];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = integers.get(i).intValue();
        }
        return ret;
    }

    public static int lower_bound(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
        return nums[low] == target ? low : -1;
    }

    public static int upper_bound(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high + 1 - low) / 2;
            if (nums[mid] > target)
                high = mid - 1;
            else
                low = mid;
        }
        return nums[low] == target ? low : -1;
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static char nextChar() throws IOException {
        return next().toCharArray()[0];
    }

    static int nextInt() throws IOException {
        return parseInt(next());
    }

    static long nextLong() throws IOException {
        return parseLong(next());
    }

    static double nextDouble() throws IOException {
        return parseDouble(next());
    }

    static String next() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public static void main(String[] args) {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
            solve();
            long lEndTime = System.currentTimeMillis();
            //System.out.println("Elapsed time in seconds: " + (double)(lEndTime - lStartTime) / 1000.0);
            in.close();
            out.close();
        } catch (Throwable e) {
            e.printStackTrace();
            exit(1);
        }
    }
}