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 B
{
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		long p = sc.nextInt();
		long q = sc.nextInt();
		long r = sc.nextInt();
		long[] arr = new long[n];
		for(int i=0;i<n;i++)
			arr[i] = sc.nextInt();

		long[] a = new long[n];
		for(int i=0;i<n;i++)
			a[i] = arr[i] * p;
		long[] b = new long[n];
		for(int i=0;i<n;i++)
			b[i] = arr[i] * q;

		long[] c = new long[n];
		for(int i=0;i<n;i++)
			c[i] = arr[i] * r;

		SparseTable bef = new SparseTable(a);
		SparseTable aft = new SparseTable(c);
		long max = -(long)(4e18) - 55;
		for(int i=0;i<n;i++)
		{
			long now = b[i];
			long q1 = a[bef.query(0, i)];
			long q2 = c[aft.query(i, n-1)];
			if(now + q1 + q2 > max)
				max = now + q1 +q2;
		}
		System.out.println(max);

	}
	static class Scanner {
		StringTokenizer st;BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public String next() throws IOException 
		{while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public long nextLong() throws IOException {return Long.parseLong(next());}
		public String nextLine() throws IOException {return br.readLine();}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public boolean ready() throws IOException {return br.ready();}
	}
	static class SparseTable {                                          

		long A[];
		int SpT[][];

		SparseTable(long[] A) 
		{
			int n = A.length;	this.A = A;
			int k = (int)Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];

			for (int i = 0; i < n; i++) 
				SpT[i][0] = i; 					// RMQ of sub array starting at index i and of length 2^0=1

			//overall time complexity = O(n log n)
			for (int j = 1; (1<<j) <= n; j++) 				
				for (int i = 0; i + (1<<j) - 1 < n; i++)    
					if (A[SpT[i][j-1]] > A[SpT[i+(1<<(j-1))][j-1]])
						SpT[i][j] = SpT[i][j-1];    		// start at index i of length 2^(j-1)
					else                  					// start at index i+2^(j-1) of length 2^(j-1)
						SpT[i][j] = SpT[i+(1<<(j-1))][j-1];
		}

		int query(int i, int j) 
		{

			int k = (int)Math.floor(Math.log(j-i+1) / Math.log(2)); // 2^k <= (j-i+1)

			if (A[SpT[i][k]] > A[SpT[j-(1<<k)+1][k]]) 
				return SpT[i][k];
			else
				return SpT[j-(1<<k)+1][k];
		} 
	}

}
