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.
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 24 20:12:17 2017

@author: savit
"""
def sign(n):
    return n//abs(n)
n,p,q,r=map(int,input().split())
A=list(map(int,input().split()))
Q=q
P=p
R=r
if(p<=0 and q<=0 and r<=0):
    print((p+q+r)*min(A))

    
elif(p>=0 and q>=0 and r>=0):
    print((p+q+r)*max(A))
elif(p*r>=0 and p<0):
    b=[]
    max1=-9999999999999999999999999999999
    for i in range(n):
        b.append((A[i],i))
    b.sort()
    mini=b[0][1]
    temp=mini
    temp2=A[mini]
    tempb=0
    while(temp>=0):
        temp2=max(A[temp],temp2)
        while(b[tempb][1]>temp):
            tempb+=1
        max1=max(p*b[tempb][0]+q*temp2 + r*A[mini],max1)
        temp-=1
    
    
    temp2=A[mini]
    tempb=0
    temp=mini
    while(temp<=n-1):
        temp2=max(A[temp],temp2)
        while(b[tempb][1]<temp):
            tempb+=1
        max1=max(r*b[tempb][0]+q*temp2 + p*A[mini],max1)
        temp+=1
    print(max1)
elif(p*r>=0 and p>=0):
    b=[]
    max1=-9999999999999999999999999999999
    for i in range(n):
        b.append((A[i],i))
    b.sort()
    mini=b[n-1][1]
    temp=mini
    temp2=A[mini]
    tempb=n-1
    while(temp>=0):
        temp2=min(A[temp],temp2)
        while(b[tempb][1]>temp):
            tempb-=1
        max1=max(p*b[tempb][0]+q*temp2 + r*A[mini],max1)
        temp-=1
    temp2=A[mini]
    tempb=n-1
    temp=mini
    while(temp<=n-1):
        temp2=min(A[temp],temp2)
        while(b[tempb][1]<temp):
            tempb-=1
        max1=max(r*b[tempb][0]+q*temp2 + p*A[mini],max1)
        #print(b[tempb][1],A.index(temp2),mini)
        temp+=1
    print(max1)
elif(r>=0):
    b=[]
    if(q>=0):
        r+=q
    else:
        p+=q
    for i in range(n):
        b.append((A[i],i))
    b.sort()
    max1=-99999999999999999999999999999999
    temp=0
    temp2=A[0]
    tempb=n-1
    while(temp<=n-1):
        temp2=min(temp2,A[temp])
        while(b[tempb][1]<temp):
            tempb-=1
        
        max1=max(max1,p*temp2+r*b[tempb][0])
        
        temp+=1
    print(max1)
elif(r<0):
    b=[]
    if(q<=0):
        r+=q
    else:
        p+=q
    for i in range(n):
        b.append((A[i],i))
    b.sort()
    max1=-9999999999999999999999999999
    temp=0
    temp2=A[0]
    tempb=0

    while(temp<=n-1):
        temp2=max(temp2,A[temp])
        while(b[tempb][1]<temp):
            tempb+=1
        max1=max(max1,p*temp2+r*b[tempb][0])
        temp+=1
    print(max1)