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.
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;

public class Codeforces429B
{
	
	InputStream in;
	PrintWriter out;
	
	void solve() 
	{
		int n=ni();
		long p[]=new long[3];
		p[0]=nl();p[1]=nl();p[2]=nl();
		long a[]=new long[n];
		for (int i=0;i<n;i++)
			a[i]=nl();
		
		long dp[][]=new long[n][3];
		SegmentTree ft[]=new SegmentTree[2];
		ft[0]=new SegmentTree(n);
		ft[1]=new SegmentTree(n);
		
		dp[0][0]=a[0]*p[0];
		dp[0][1]=dp[0][0]+a[0]*p[1];
		dp[0][2]=dp[0][1]+a[0]*p[2];
		ft[0].updateValue(n,0, dp[0][0]);
		//tr(dp[0][0]+" "+ft[0].getSum(n, 0, 0));
		ft[1].updateValue(n,0, dp[0][1]);
		//tr(dp[0][0]+" "+ft[0].getSum(n, 0, 0));
		long ans=dp[0][2];
		
		for (int i=1;i<n;i++)
		{
			dp[i][0]=a[i]*p[0];
			ft[0].updateValue(n,i, dp[i][0]);
			//tr(dp[i][0]+" "+ft[0].getSum(n, 0, i));
			dp[i][1]=a[i]*p[1]+ft[0].getSum(n, 0, i);
			ft[1].updateValue(n,i, dp[i][1]);
			//tr(dp[i][1]+" "+ft[1].getSum(n, 0, i));
			dp[i][2]=a[i]*p[2]+ft[1].getSum(n, 0, i);
			ans=Math.max(ans, dp[i][2]);
			//tr(ans);
		}
		out.println(ans);
	}
	
	class SegmentTree {
		long st[];

		SegmentTree(int n) {

			int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));

			int max_size = 2 * (int) Math.pow(2, x) - 1;

			st = new long[max_size];

			Arrays.fill(st, Long.MIN_VALUE);
		}

		int getMid(int s, int e) {
			return (s + e) >> 1;
		}

		long getSumUtil(int ss, int se, int qs, int qe, int si) {

			if (qs <= ss && qe >= se)
				return st[si];

			if (se < qs || ss > qe)
				return Long.MIN_VALUE;

			int mid = getMid(ss, se);
			return Math.max(getSumUtil(ss, mid, qs, qe, 2 * si + 1) ,getSumUtil(mid + 1, se, qs, qe, 2 * si + 2));
		}

		void updateValueUtil(int ss, int se, int i, long val, int si) {

			if (i < ss || i > se)
				return;

			
			if (se != ss) {
				int mid = getMid(ss, se);
				updateValueUtil(ss, mid, i, val, 2 * si + 1);
				updateValueUtil(mid + 1, se, i, val, 2 * si + 2);
				st[si]=Math.max(st[2*si+1], st[2*si+2]);
			}
			else
				st[si] = val;
		}

		void updateValue(int n, int i, long val) {

			if (i < 0 || i > n - 1) {
				System.out.println("Invalid Input");
				return;
			}
			updateValueUtil(0, n - 1, i, val, 0);
		}

		long getSum(int n, int qs, int qe) {

			if (qs < 0 || qe > n - 1 || qs > qe) {
				System.out.println("Invalid Input");
				return -1;
			}
			return getSumUtil(0, n - 1, qs, qe, 0);
		}

	}

	
	
	void run() throws Exception 
	{
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
		
	}
	public static void main(String[] args) throws Exception 
	{
		new Codeforces429B().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() 
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) 
		{
			ptrbuf = 0;
			try 
			{
				lenbuf = in.read(inbuf);
			}
			catch (IOException e) 
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) 
	{
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() 
	{
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() 
	{
		return Double.parseDouble(ns());
	}
	
	private char nc() 
	{
		return (char) skip();
	}
	
	private String ns() 
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) 
		{ // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) 
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) 
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) 
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) 
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() 
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			} 
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}
		
		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			}
			else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}