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.util.*;
import java.math.*;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class Main {
	
	public static void main(String[] args) {
		
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB calc = new TaskB();
        calc.solve(  in , out);
        out.close();
    }
	
	class Pair{
		
		int first;
		int second;
		
		Pair(int f , int s) {
			first = f;
			second = s;
		}
		
	}
	
	static class TaskB {
		InputReader in;
        PrintWriter out;
		static int MAXN = 100001;
		
		public void solve(InputReader in , PrintWriter out) {
			
			int n = in.nextInt();

			
			long p = in.nextInt();
			long q = in.nextInt();
			long r = in.nextInt();
			
			long a[] = new long[n];
			long neg[] = new long[n];
			long pos[] = new long[n];
			long negr[] = new long[n];
			long posr[] = new long[n];
			
			for (int i = 0; i < n; i ++ ) {
				a[i] = in.nextLong();
				neg[i] = a[i];
				pos[i] = a[i];
				negr[i] = a[i];
				posr[i] = a[i];
			}
			for ( int i = 1; i < n; i ++ ) {
				neg[i] = Math.min(neg[i], neg[ i - 1 ]);
				pos[i] = Math.max(pos[i], pos[ i - 1 ]);
			}
			
			for ( int i = n - 2; i >= 0; i -- ) {
				negr[i] = Math.min(negr[i], negr[ i + 1]);
				posr[i] = Math.max(posr[i], posr[ i + 1]);
			}
			
			long res = (long)p * a[0] + q * a[0] + r * a[0];
			
			for ( int i = 0; i < n; i ++ ) {
				long t = 0;
				if ( p < 0 ) t = t + (long)p * neg[i];
				else t = t + (long)p * pos[i];
				
				t = t  + q * a[i];
				
				if ( r < 0 ) t = t + (long)r * negr[i];
				else t = t + (long)r * posr[i];
				
				res = Math.max(res , t);
			}
	
			out.println(res);
			
		}
	}
	
	
	
	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536 / 2);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong(){
        	return Long.parseLong(next());
        }

    }
	
}
