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.Scanner;
import java.lang.Math;

public class Solution {
  public static void main(String[] args) {
    
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int p = in.nextInt();
    int q = in.nextInt();
    int r = in.nextInt();
    int[] arr = new int[n];
    int[] prefixMax = new int[n];
    int[] suffixMax = new int[n];
    for(int i =0;i<n;i++){
      arr[i]=in.nextInt();
    }
    int j=n-1;
    for(int i=0;i<n;i++){
      if(i==0){
         prefixMax[i] = arr[i];
      }else{
        if(p>0){
      		prefixMax[i]= Math.max(prefixMax[i-1],arr[i]);
         }
        else{
          prefixMax[i]= Math.min(prefixMax[i-1],arr[i]);
        }
      }
      
      if(j==n-1){
         suffixMax[j] = arr[j];
      }else{
        if(r>0){
      		suffixMax[j]= Math.max(suffixMax[j+1],arr[j]);}
        else{
          suffixMax[j]= Math.min(suffixMax[j+1],arr[j]);
        }
      }
      j--;
    }
    long ans = Long.MIN_VALUE;
    for(int i =0;i<n;i++){
      long v1 = (long)p*(long)prefixMax[i];
      long v2 = (long)q*(long)arr[i];
      long v3 = (long)r*(long)suffixMax[i];
      long temp = v1+v2+v3;
      ans = Math.max(ans,temp);      
    }
    System.out.println(ans);
    

  }
}
