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 sys
input1 = input().split()
input1= list(map(int,input1))
n= input1[0]
p= input1[1]
q= input1[2]
r= input1[3]
arr = input().split()
arr = list(map(int,arr))
def max_check(num1,num2):
    if num1>num2:
        return num1
    else:
        return num2
pre_max= []
pre_max.append(p*arr[0])
for i in range(1,n):
    val=max_check(pre_max[i-1],p*arr[i])
    pre_max.insert(i,val)

sub_max = [None]*n
sub_max[n-1] = r*arr[n-1]
for j in reversed(range(n-1)):
    sub_max[j]=max_check(sub_max[j+1],r*arr[j])


ans = -999999999999999999999

for k in range(n):
    max_val = pre_max[k] + q*arr[k]+ sub_max[k]
    ans = max_check(max_val,ans)
print(ans)


# 545252056 991639306 598873846 576383007 -151449019 508543232 638597388 543974959 821200465 -682276106 -728174100 -200195453 284269278 448174703 -69036646 204240635 705570395 -783011295 -107568450 77507090 62743075 218501692 -781721191 -538059674 634216709 -883057654 -956452702 -169515904 -986717881 22679327 150133139 -700167235 9639565 991921792 543266162 -177351065 784430744 -238005589 834623613 -938202528 558903904 -780925656 636486194 690553411 -456498198 -707456888 ...
# 905454060