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.math.BigInteger;
import java.util.Scanner;

public class MarvoloGauntsRing {
	public static void memoriaR(BigInteger a, BigInteger orig[], BigInteger memoMax [], BigInteger memoMin [] ){
		BigInteger mult = new BigInteger("-1000000000000000000000000000000");
		BigInteger mult2 = new BigInteger("1000000000000000000000000000000");
		for (int i = orig.length-1; i >= 0 ; i--) {
			mult = mult.max(a.multiply(orig[i]));
			mult2 = mult2.min(a.multiply(orig[i]));
			memoMax[i]= mult;
			memoMin[i]= mult2;
		}
	}
	public static void memoriaP(BigInteger a, BigInteger orig[], BigInteger memoMax [], BigInteger memoMin [] ){
		BigInteger mult = new BigInteger("-1000000000000000000000000000000");
		BigInteger mult2 = new BigInteger("1000000000000000000000000000000");
		for (int i = 0; i < orig.length ; i++) {
			mult = mult.max(a.multiply(orig[i]));
			mult2 = mult2.min(a.multiply(orig[i]));
			memoMax[i]= mult;
			memoMin[i]= mult2;
		}
	}
	public static BigInteger maximoValorDP(int n , BigInteger p, BigInteger q, BigInteger r, BigInteger arr[]){
		BigInteger sum = new BigInteger("-1000000000000000000000000000000");

		BigInteger memoriaPmax [] = new BigInteger [n];
		BigInteger memoriaPmin [] = new BigInteger [n];
		BigInteger memoriaRmax [] = new BigInteger [n];
		BigInteger memoriaRmin [] = new BigInteger [n];
	

		memoriaP(p, arr, memoriaPmax, memoriaPmin);
		memoriaR(r, arr, memoriaRmax, memoriaRmin);
		
		for (int i = 0; i < arr.length; i++) {
			sum = sum.max((q.multiply(arr[i]).add(memoriaPmax[i].max(memoriaPmin[i])).add(memoriaRmax[i].max(memoriaRmin[i]))));
			
		}
		return sum;
	}
	public static BigInteger BruteForce(int n , BigInteger p, BigInteger q, BigInteger r, BigInteger arr[]){
		BigInteger sum = new BigInteger("-1000000000000000000000000000000");

		for (int i = 0; i < arr.length; i++) {
			for (int j = i; j < arr.length; j++) {
				for (int j2 = j; j2 < arr.length; j2++) {

					sum = sum.max((p.multiply(arr[i]).add(q.multiply(arr[j]))).add(r.multiply(arr[j2])));
				}
			}
		}
		return sum;
	}
	public static void mostrar(BigInteger arr[]) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+ " ");
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); 
		BigInteger p = sc.nextBigInteger();
		BigInteger q = sc.nextBigInteger();
		BigInteger r = sc.nextBigInteger();

		BigInteger arr [] = new BigInteger [n];

		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextBigInteger();
		}
		System.out.println(maximoValorDP(n, p, q, r, arr));
	}

}
