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

/*
TASK: CF436B
LANG: JAVA
 */
public class CF436B {
    static int n;
    static long p , q , r;
    static long[] a;
    static long[] dpp , dpq , dpr;
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in); //new FileInputStream(new File("CF436B.in")));
        //PrintWriter out = new PrintWriter(new File("CF436B.out"));
        n = in.nextInt();
        dpp = new long[n];
        dpq = new long[n];
        dpr = new long[n];
        a = new long[n];
        p = in.nextLong();
        q = in.nextLong();
        r = in.nextLong();
        for(int i = 0;i < n; i++)a[i] = in.nextLong();
        dpr[n-1] = r*a[n-1];
        dpq[n-1] = q*a[n-1] + dpr[n-1];
        dpp[n-1] = p*a[n-1] + dpq[n-1];
        for(int i = n-2; i >= 0; i--){
            dpr[i] = Math.max(dpr[i+1] , r*a[i]);
            dpq[i] = Math.max(dpq[i+1] , q*a[i] + dpr[i]);
            dpp[i] = Math.max(dpp[i+1] , p*a[i] + dpq[i]);
        }
        System.out.println(dpp[0]);

    }

    private static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        boolean isEndline(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

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

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

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }
    }
}
