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.util.*;
import java.io.*;
public class ring {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader in = new BufferedReader(new FileReader("test.in"));
		PrintStream out = System.out;
		String line = in.readLine().trim(), lines[] = line.split(" ");

		int n = Integer.parseInt(lines[0]);
		long p = Integer.parseInt(lines[1]), 
			q = Integer.parseInt(lines[2]), r = Integer.parseInt(lines[3]);
		long[] arr = new long[n];
		lines = in.readLine().split(" ");
		for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(lines[i]);

		long[] prep = new long[n], pren = new long[n], sufp = new long[n], sufn = new long[n];
		Arrays.fill(prep, -(1<<27) + 5);
		Arrays.fill(pren, (1<<27) + 5);
		Arrays.fill(sufp, -(1<<27) + 5);
		Arrays.fill(sufn, (1<<27) + 5);
		prep[0] = pren[0] = arr[0];
		for (int i = 1; i < n; i++) {
			prep[i] = Math.max(prep[i-1], arr[i]);
			pren[i] = Math.min(pren[i-1], arr[i]);
		}
		sufp[n-1] = sufn[n-1] = arr[n-1];
		for (int i = n-2; i >= 0; i--) {
			sufp[i] = Math.max(sufp[i+1], arr[i]);
			sufn[i] = Math.min(sufn[i+1], arr[i]);
		}
		// out.println(Arrays.toString(sufp));

		long ans = Long.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			if (p >= 0) {
				if (r >= 0) {
					ans = Math.max(ans, p*prep[i] + q*arr[i] + r*sufp[i]);
				} else {
					ans = Math.max(ans, p*prep[i] + q*arr[i] + r*sufn[i]);
				}
			} else {
				if (r >= 0) {
					ans = Math.max(ans, p*pren[i] + q*arr[i] + r*sufp[i]);
				} else {
					ans = Math.max(ans, p*pren[i] + q*arr[i] + r*sufn[i]);
				}
			}
		}
		out.println(ans);
	}
}