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.*;
import java.text.*;
import java.math.*;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {

        public void solve(int testNumber, 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];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }
            long[] ap = new long[n], aq = new long[n], ar = new long[n];
            for (int i = 0; i < n; i++) {
                ap[i] = a[i] * p;
                aq[i] = a[i] * q;
                ar[i] = a[i] * r;
            }
            long maxValue = Long.MIN_VALUE;
//            for (int i = n - 1; i >= 0; i++) {
//                if (ap[i] > maxValue) {
//                    maxIndex = i;
//                    maxValue = ap[i];
//                }
//                ap[i] = maxIndex;
//            }
//            maxIndex = -1;
//            maxValue = Long.MIN_VALUE;
//            for (int i = n - 1; i >= 0; i++) {
//                if (aq[i] > maxValue) {
//                    maxIndex = i;
//                    maxValue = ap[i];
//                }
//                aq[i] = maxIndex;
//            }

            maxValue = Long.MIN_VALUE;
            for (int i = n - 1; i >= 0; i--) {
                if (ar[i] > maxValue) {
                    maxValue = ar[i];
                }
                ar[i] = maxValue;
            }
            

            for(int i  = 0; i<n; i++){
                aq[i] += ar[i];                
            }
            
            maxValue = Long.MIN_VALUE;
            for (int i = n - 1; i >= 0; i--) {
                if (aq[i] > maxValue) {
                    maxValue = aq[i];
                }
                aq[i] = maxValue;
            }

            
            for(int i  = 0; i<n; i++){
                ap[i] += aq[i];                
            }
            maxValue = Long.MIN_VALUE;
            for (int i = n - 1; i >= 0; i--) {
                if (ap[i] > maxValue) {
                    maxValue = ap[i];
                }
                ap[i] = maxValue;
            }
            out.println(maxValue);
        }
    }

    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.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());
        }

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

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

    }
}
