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.
n,p,q,r=map(int,input().split())
a=list(map(int,input().split()))
z=-(100000000000000000000000000000)**1000
if q >=0 and p >=0 and r>=0:
    c=-100000000000
    for i in range(len(a)):
        if a[i]>c:
            c=a[i]
    print(c*(q+p+r))
else:
    if q <=0 and p <=0 and r<=0:
        c=100000000000
        for i in range(len(a)):
            if a[i]<c:
                c=a[i]
        print(c*(q+p+r))
    else:
        b2=a[0]*p
        b=[b2]*n
        for i in range(1,len(a)):
            if a[i]*p>b[i-1]:
                b[i]=a[i]*p
            else:
                b[i]=b[i-1]
        t2=a[n-1]*r
        t=[t2]*n
        for i in range(n-2,-1,-1):
            if a[i]*r>t[i+1]:
                t[i]=a[i]*r
            else:
                t[i]=t[i+1]
        for i in range(n):
            if a[i]*q+b[i]+t[i]>z:
                
                z=a[i]*q+b[i]+t[i]
        print(z)
            
            
