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.FileNotFoundException;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        try (PrintWriter out = new PrintWriter(outputStream)) {
            TaskB solver = new TaskB();
            solver.solve(1, in, out);
        }
    }
}
class TaskB {
    long minVal = Long.MIN_VALUE;
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        long p = in.nextLong();
        long q = in.nextLong();
        long r = in.nextLong();
        long maxP = minVal;
        long maxQ = minVal;
        long maxR = minVal;
        for (int i = 0; i < n; ++i) {
            long tmpNum = in.nextLong();
            maxP = Math.max(maxP, p * tmpNum);
            maxQ = Math.max(maxQ, maxP + q * tmpNum);
            maxR = Math.max(maxR, maxQ + r * tmpNum);
        }
        out.println(maxR);
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;
    public InputReader(InputStream stream) throws FileNotFoundException {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(nextLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong() {
        return Long.parseLong(next());
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    public int[] nextInts(int n) {
        int a[] = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = nextInt();
        return a;
    }
    int[] getPrimes(int n) {
        int a[] = new int[n];
        Arrays.fill(a, 1);
        a[0] = a[1] = 0;
        for (int i = 2; i * i < n; ++i) {
            if (a[i] == 1) {
                for (int j = i * i; j < n; j += i)
                    a[j] = 0;
            }
        }
        return a;
    }
}
