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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractMap;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
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);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] factors = new long[3];
            for (int i = 0; i < 3; ++i) factors[i] = in.nextLong();
            long[] v = new long[n];
            TreeMap<Long, Integer> numsBefore = new TreeMap<>();
            TreeMap<Long, Integer> numsAfter = new TreeMap<>();
            for (int i = 0; i < n; ++i) {
                v[i] = in.nextLong();
                numsAfter.put(v[i], numsAfter.getOrDefault(v[i], 0) + 1);
            }
            long ans = -4000000000000000000L;
            for (int i = 0; i < n; ++i) {
                long val1 = factors[1] * v[i];
                long val2 = factors[0] * v[i];
                if (!numsBefore.isEmpty()) {
                    val2 = Math.max(val2,
                            Math.max(factors[0] * numsBefore.firstKey(),
                                    factors[0] * numsBefore.lastKey())
                    );
                }
                long val3 = factors[2] * v[i];
                val3 = Math.max(val3,
                        Math.max(factors[2] * numsAfter.firstKey(),
                                factors[2] * numsAfter.lastKey())
                );
                ans = Math.max(ans, val1 + val2 + val3);
                numsAfter.put(v[i], numsAfter.get(v[i]) - 1);
                if (numsAfter.get(v[i]) == 0) numsAfter.remove(v[i]);
                numsBefore.put(v[i], numsBefore.getOrDefault(v[i], 0) + 1);
            }
            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536 / 2);
            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());
        }

    }
}

