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 {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }
    static class Solver {
        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long p = in.nextInt();
            long q = in.nextInt();
            long r = in.nextInt();
            long[] a = new long[n];
            long x = Long.MIN_VALUE;
            long min = Long.MAX_VALUE;
            long max = Long.MIN_VALUE;
            long[] minto = new long[n];
            long[] maxto = new long[n];
            long[] minfrom = new long[n];
            long[] maxfrom = new long[n];
            int[] indminto = new int[n];
            int[] indmaxto = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextLong();
                boolean minchanged = false;
                boolean maxchanged = false;
                if (max < a[i]) {
                    max = a[i];
                    indmaxto[i] = i;
                    maxchanged = true;
                }
                if (min > a[i]) {
                    min = a[i];
                    indminto[i] = i;
                    minchanged = true;
                }
                minto[i] = min;
                maxto[i] = max;
                if (!minchanged) {
                    indminto[i] = indminto[i - 1];
                }
                if (!maxchanged) {
                    indmaxto[i] = indmaxto[i - 1];
                }
            }
            min = Long.MAX_VALUE;
            max = Long.MIN_VALUE;
            for (int i = n - 1; i >= 0; --i) {
                if (max < a[i]) {
                    max = a[i];
                }
                if (min > a[i]) {
                    min = a[i];
                }
                minfrom[i] = min;
                maxfrom[i] = max;
            }
            for (int i = 0; i < n; ++i) {
                boolean maxused = false;
                boolean minused = false;
                long temp = 0;
                if (q < 0) {
                    temp += q * minto[i];
                    minused = true;
                } else {
                    temp += q * maxto[i];
                    maxused = true;
                }
                if (p < 0) {
                    if (minused) {
                        if (indminto[i] == i) {
                            temp += p * minto[i];
                        } else {
                            temp += p * minto[indminto[i]];
                        }
                    } else if (maxused) {
                        if (indmaxto[i] == i) {
                            temp += p * minto[i];
                        } else {
                            temp += p * minto[indmaxto[i]];
                        }
                    }
                } else {
                    if (minused) {
                        if (indminto[i] == i) {
                            temp += p * maxto[i];
                        } else {
                            temp += p * maxto[indminto[i]];
                        }
                    } else if (maxused) {
                        if (indmaxto[i] == i) {
                            temp += p * maxto[i];
                        } else {
                            temp += p * maxto[indmaxto[i]];
                        }
                    }
                }
                temp += r * (r < 0 ? minfrom[i] : maxfrom[i]);
                long tmp = q * a[i] + p * (p < 0 ? minto[i] : maxto[i]) + r * (r < 0 ? minfrom[i] : maxfrom[i]);
                temp = Math.max(temp, tmp);
                x = Math.max(x, temp);
            }
            out.println(x);
        }
    }
    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.hasMoreElements()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public String nextLine() {
            String s = "";
            try {
                s = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return s;
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}