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.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

public class Main {
	
	static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[256]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
	
	static class FastScanner {

	    private final BufferedReader bufferedReader;
	    private StringTokenizer stringTokenizer;

	    public FastScanner() {
	        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public String next() {
	        while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
	            try {
	                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException("Can't read next value", e);
	            }
	        }
	        return stringTokenizer.nextToken();
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

	    public double nextDouble() {
	        return Double.parseDouble(next());
	    }

	    public String nextLine(){
	        String str = "";
	        try {
	            str = bufferedReader.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	    }
	}
	
	static void closeall() throws IOException{
		printWriter.close();
		sc.close();
		in.close();
	}
	static Scanner sc = new Scanner(System.in);
	static Reader in = new Reader();
	static FastScanner fastScanner = new FastScanner();
	static PrintWriter printWriter = new PrintWriter(new BufferedOutputStream(System.out));
	static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
	static long INF = (long)(1e18);
	
	int V,E;
	ArrayList<Integer> adj[];
	Main(int v,int e){
		V=v;
		E=e;
		adj=new ArrayList[v];
		for(int i=0;i<v;i++)
			adj[i] = new ArrayList<>();
	}
	void addEdge(int u,int v){
		adj[u].add(v);
		adj[v].add(u);
	}
	
	
	public static void main(String args[])throws IOException{
		int n = in.nextInt();
		long p = in.nextLong();
		long q = in.nextLong();
		long r = in.nextLong();
		long[] a = new long[n];
		for(int i=0;i<n;i++)
			a[i]=in.nextLong();
		long[] b = new long[n];
		long[] c = new long[n];
		for(int i=0;i<n;i++)
			b[i]=a[i]*q;
		for(int i=0;i<n;i++)
			c[i]=a[i]*r;
		for(int i=0;i<n;i++)
			a[i]=a[i]*p;
		/*long maxb[] = new long[n];
		long maxc[] = new long[n];
		maxb[n-1]=b[n-1];
		maxc[n-1]=c[n-1];
		long mb=b[n-1],mc=c[n-1];
		for(int i=n-2;i>=0;i--){
			if(b[i]>=mb && c[i]>=mc){
				maxb[i]=b[i];
				mb=b[i];
				maxc[i]=c[i];
				mc=c[i];
			}
			else if(b[i]>=mb){
				maxb[i]=b[i];
				mb=b[i];
				maxc[i]=mc;
			}
			else if(c[i]>=mc){
				maxb[i]=mb;
				maxc[i]=mc;
				mc=c[i];
			}
			else{
				maxb[i]=mb;
				maxc[i]=mc;
			}
		}
		long ans[] = new long[n];
		for(int i=0;i<n;i++)
			ans[i]=a[i]+maxb[i]+maxc[i];
		
		long mans=Long.MIN_VALUE;
		for(int i=0;i<n;i++)
			mans=(long)Math.max(mans, ans[i]);
		printWriter.println(mans);*/
		long s[] = new long[n];
		/*s[n-1]=b[n-1]+c[n-1];
		int maxB=n-1,maxC=n-1;
		for(int i=n-2;i>=0;i--){
			if(b[i]>b[maxB])
				maxB=i;
			
			if (c[i] + b[maxB] > s[i+1]) {
	            s[i] = c[i] + b[maxB];
	        }
		}*/
		s[n-1]=b[n-1]+c[n-1];
		int maxC=n-1;
		for(int i=n-2;i>=0;i--){
			if(c[i]>=c[maxC])
				maxC=i;
			s[i]=(long)Math.max(s[i+1], b[i]+c[maxC]);
		}
		long ans[] = new long[n];
		BigInteger f = new BigInteger("-3000000000000000000");
		long maxa=a[0];
		for(int i=0;i<n;i++){
			if(a[i]>maxa)
				maxa=a[i];
			BigInteger g = new BigInteger("0");
			g=g.add(new BigInteger(Long.toString(s[i])));
			g=g.add(new BigInteger(Long.toString(maxa)));
			f=f.max(g);
		}
		printWriter.println(f);
		closeall();
	}
}
