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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B855 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()),
			p=Integer.parseInt(st.nextToken()),
			q=Integer.parseInt(st.nextToken()),
			r=Integer.parseInt(st.nextToken());
		
		ArrayList<Long> arr = new ArrayList<>();
		ArrayList<ArrayList<Long>> dp=new ArrayList<>();
		st=new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			arr.add(Long.parseLong(st.nextToken()));
		
		// (p·ai) + q·aj + r·ak
		dp.add(new ArrayList<>());
		dp.get(0).add((long) (p*arr.get(0)));
		for(int i=1;i<n;i++)
			dp.get(0).add(Math.max(dp.get(0).get(i-1), p*arr.get(i)));
		
		// (p·ai + q·aj) + r·ak
		dp.add(new ArrayList<>());
		dp.get(1).add(dp.get(0).get(0)+q*arr.get(0));
		for(int i=1;i<n;i++)
			dp.get(1).add(Math.max(dp.get(1).get(i-1), dp.get(0).get(i)+q*arr.get(i)));
		
		// (p·ai + q·aj + r·ak)
		dp.add(new ArrayList<>());
		dp.get(2).add(dp.get(1).get(0)+r*arr.get(0));
		for(int i=1;i<n;i++)
			dp.get(2).add(Math.max(dp.get(2).get(i-1), dp.get(1).get(i)+r*arr.get(i)));

//		for (ArrayList<Long> arrayList : dp) {
//			for (Long integer : arrayList) {
//				System.out.print(integer+" ");
//			}
//			System.out.println();
//		}
		
		System.out.println(dp.get(2).get(n-1));
			
	}
}
