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 B855 {

	public static void main(String[] args) throws IOException {
		IO io = new IO(System.in);

		int n = io.nextInt();
		long p = io.nextLong();
		long q = io.nextLong();
		long r = io.nextLong();
		
		long[] a = new long[n];
		for (int i =0; i < a.length; i++) {
			a[i]=io.nextLong();
		}
		
		long[] min_left = new long[n];
		long[] max_left = new long[n];
		long[] min_right = new long[n];
		long[] max_right = new long[n];
		min_left[0]=a[0];
		max_left[0]=a[0];
		for (int i = 1; i < n; i++) {
			min_left[i] = Math.min(min_left[i-1], a[i]);
			max_left[i] = Math.max(max_left[i-1], a[i]);
		}
		min_right[n-1]=a[n-1];
		max_right[n-1]=a[n-1];
		for (int i = n-2; i >=0; i--) {
			min_right[i] = Math.min(min_right[i+1], a[i]);
			max_right[i] = Math.max(max_right[i+1], a[i]);
		}
		
		long best = Long.MIN_VALUE;
		for (int j = 0; j < n; j++) {
			// place j here
			long cur = q*a[j];
			if (p < 0) {
				cur += p*min_left[j];
			} else {
				cur += p*max_left[j];
			}
			if (r < 0) {
				cur += r*min_right[j];
			} else {
				cur += r*max_right[j];
			}
			if (cur>best) best=cur;
		}
		
		io.println(best);
		
		io.close();
	}

	static class IO extends PrintWriter {
		static BufferedReader r;
		static StringTokenizer t;

		public IO(InputStream i) {
			super(new BufferedOutputStream(System.out));
			r = new BufferedReader(new InputStreamReader(i));
			t = new StringTokenizer("");
		}

		public String next() throws IOException {
			while (!t.hasMoreTokens()) {
				t = new StringTokenizer(r.readLine());
			}
			return t.nextToken();
		}

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

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

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