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 Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
    static final long N = (long) (1e15);
   
	public static void main(String[] args) {
		FastReader sc = new FastReader();
	   
		  int n = sc.nextInt();
		  long p = sc.nextLong(), q = sc.nextLong(),r = sc.nextLong();
		  int[] a = new int[n+1];
		  for(int i=1;i<=n;++i) 
			  a[i] = sc.nextInt();
		  int[] low = new int[n+2];
		  int[] high = new int[n+2];
		  Arrays.fill(low,Integer.MAX_VALUE);
		  Arrays.fill(high,Integer.MIN_VALUE);
		  for(int i=1;i<=n;++i) {
			  low[n-i+1] = Math.min(a[n-i+1], low[n-i+2]);
			  high[n-i+1] = Math.max(a[n-i+1],high[n-i+2]);
		  }
		 
		  long ans = Long.MIN_VALUE,min = Integer.MAX_VALUE,max = Integer.MIN_VALUE;
		  for(int i=1;i<=n;++i) {
			  max = Math.max(max,a[i]);
			  min = Math.min(min,a[i]);
			  ans = Math.max(ans,Math.max(p*min, p*max) + q*a[i] + Math.max(r*low[i],r*high[i]));
		  }
		  out.println(ans);
		 
		  
		 
		   out.close();			
		}
	 
	}