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·a_{i} + q·a_{j} + r·a_{k} for given p, q, r and array a_1, a_2, ... a_{n} 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 ( - 10^9 ≤ p, q, r ≤ 10^9, 1 ≤ n ≤ 10^5).

Next line of input contains n space separated integers a_1, a_2, ... a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Output a single integer the maximum value of p·a_{i} + q·a_{j} + r·a_{k} 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.

Difficulty: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n,p,q,r=map(int,input().split())

a=list(map(int,input().split()))

s1=[a[i]*p for i in range(n)]

s2=[]
m=s1[0]
for i in range(n):
    m=max(m,s1[i])
    s2.append(m+a[i]*q)

s3=[]
m=s2[0]
for i in range(n):
    m=max(m,s2[i])
    s3.append(m+a[i]*r)

print(max(s3))

n, p, q, r = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
mx1 = [0] * n
mx1[0] = p * a[0]
for i in range(1, n):
    mx1[i] = max(p * a[i], mx1[i - 1])
mx2 = [0] * n
mx2[n - 1] = r * a[n - 1]
for i in range(n - 2, -1, -1):
    mx2[i] = max(r * a[i], mx2[i + 1])
ans = mx1[0] + q * a[0] + mx2[0]
for i in range(1, n):
    ans = max(ans, q * a[i] + mx1[i] + mx2[i])
print(ans)

def list_input():
    return list(map(int,input().split()))
def map_input():
    return list(map(int,input().split()))
def map_string():
    return input().split()
    
n,p,q,r = map_input()
a = [p,q,r]
b = list_input()
ans = 0
INF = -100000000000000000000000
dp = [INF]*(n+5)
dp2 = [INF]*(n+5)
dp3 = [INF]*(n+5)
for i in range(n): dp[i] = p*b[i]
for i in range(1,n): dp[i] = max(dp[i],dp[i-1])
for i in range(n): dp2[i] = q*b[i]+dp[i]
for i in range(1,n): dp2[i] = max(dp2[i],dp2[i-1])
for i in range(n): dp3[i] = r*b[i]+dp2[i]
for i in range(1,n): dp3[i] = max(dp3[i],dp3[i-1])
print(dp3[n-1])


def main():
    n, p, q, r = list(map(int, input().split()))
    a = list(map(int, input().split()))
    dp = [float('-inf') for _ in range(n)]
    dp[-1] = r * a[-1]

    for i in range(n - 2, -1, -1):
        dp[i] = max(r * a[i], dp[i + 1])

    dp2 = [float('-inf') for _ in range(n)]
    dp2[-1] = (q + r) * a[-1]
    for i in range(n - 2, -1, -1):
        dp2[i] = max(q * a[i] + dp[i], dp2[i + 1])

    dp3 = [float('-inf') for _ in range(n)]
    dp3[-1] = (p + q + r) * a[-1]
    for i in range(n - 2, -1, -1):
        dp3[i] = max(p * a[i] + dp2[i], dp3[i + 1])

    print(dp3[0])

main()


n, p, q, r = map(int, input().split())
A = list(map(int, input().split()))

P = [p * a for a in A]
Q = [q * a for a in A]
R = [r * a for a in A]

ans = - (10 ** 20)

for i in range(1, n):
	P[i] = max(P[i], P[i - 1])

PQ = [0 for i in range(n)]

for i in range(n):
	PQ[i] = P[i] + Q[i]

	if i: 
		PQ[i] = max(PQ[i], PQ[i - 1])

for i in range(n):
	ans = max(ans, PQ[i] + R[i])

print(ans)

n, p, q, r = list(map(int, input().split()))
a = list(map(int, input().split()))

pa = [p*a[0]]*n
for i in range(1, n):
    pa[i] = max(pa[i-1], p*a[i])
    
qa = [q*a[0] + pa[0]]*n
for i in range(1, n):
    qa[i] = max(qa[i-1], q*a[i] + pa[i])

ra = [r*a[0] + qa[0]]*n
for i in range(1, n):
    ra[i] = max(ra[i-1], r*a[i] + qa[i])
    
print(max(ra))
    


n, p, q, r = map(int, input().split())
a = list(map(int, input().split()))
max_pa_i = [0] * n
max_pa_i[0] = a[0] * p
for i in range(1, n):
    max_pa_i[i] = max(a[i] * p, max_pa_i[i - 1])
max_ra_k = [0] * n
max_ra_k[-1] = a[-1] * r
for i in range(n - 2, -1, -1):
    max_ra_k[i] = max(a[i] * r, max_ra_k[i+1])
x = -10 ** 19
for i in range(n):
    x = max(x, max_pa_i[i] + q * a[i] + max_ra_k[i])
print(x)

s=input()
c=s.split(' ')
for i in range(4):
    c[i]=int(c[i])
s=input()
a=s.split(' ')
for i in range(c[0]):
    a[i]=int(a[i])
    a[i]=[(c[1])*a[i],(c[2])*a[i],(c[3])*a[i]]
dp=[[0,0,0] for i in range(c[0])]
m1=-1000000000000000001
m2=-2000000000000000001
m3=-3000000000000000001
for i in range(c[0]):
    m1=max(m1,a[i][0])
    m2=max(m2,m1+a[i][1])
    m3=max(m3,m2+a[i][2])
print (m3)


n, p, q, r = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
crmx, crmn = [a[n - 1]] * n, [a[n - 1]] * n

for i in range(n - 2, -1, -1):
    crmx[i] = max(crmx[i + 1], a[i])
    crmn[i] = min(crmn[i + 1], a[i])

ans = 0 - 10 ** 21

mn, mx = a[0], a[0]

for i in range(n):
    cans = q * a[i]
    mx = max(mx, a[i])
    mn = min(mn, a[i])
    cans += max(mx * p, mn * p)
    cans += max(crmx[i] * r, crmn[i] * r)
    ans = max(ans, cans)

print(ans)


n, p, q, r = list(map(int, input().split()))
a = list(map(int, input().split()))[::-1]

INF = -10 ** 30

answer = INF
dp = [INF, INF, INF]

for i in range(n):
    dp[0] = max(dp[0], r * a[i])
    dp[1] = max(dp[1], q * a[i] + dp[0])
    dp[2] = max(dp[2], p * a[i] + dp[1])
    answer = max(answer, dp[2])

print(answer)


n,p,q,r = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))

max1 = {}
min1 = {}
max2 = {}
min2 = {}
maxval1 = a[0]
minval1 = a[0]
maxval2 = a[n-1]
minval2 = a[n-1]

for i in range(n):
  j = n-1-i
  maxval1 = max(maxval1, a[i])
  max1[i] = maxval1
  minval1 = min(minval1, a[i])
  min1[i] = minval1
  maxval2 = max(maxval2, a[j])
  max2[j] = maxval2
  minval2 = min(minval2, a[j])
  min2[j] = minval2


x = None
for i in range(n):
  y = q*a[i]
  if p > 0:
    y += p*max1[i]
  else:
    y += p*min1[i]
  if r > 0:
    y += r*max2[i]
  else:
    y += r*min2[i]
  if x is None or x < y:
    x = y

print(x)

(n,p,q,r2)=list(map(int,input().split()));
a=list(map(int,input().split()));
#print(a);
#print(p);
small=10**9+1;
large=-10**9-1;
infa=10**9+1;
infb=-10**9-1;
l=[];
r=[];
for i in range(0,n):
    small=min(small,a[i]);
    large=max(large,a[i]);
    l.append((small,large));
small=10**9+1;
large=-10**9-1;
for i in range(n-1,-1,-1):
    small=min(small,a[i]);
    large=max(large,a[i]);
    r.append((small,large));
r=r[-1::-1];
#print(l);
#print(r);
s=0;
x=a[0];
maxs=x*p+x*q+x*r2;
for i in range(n):
    s=0;
    if(p>0):
        s=s+p*l[i][1];
    else:
        s=s+p*l[i][0];
    if(r2>0):
        s=s+r2*r[i][1];
    else:
        s=s+r2*r[i][0];
    s=s+q*a[i];
    #print(s);
        
    maxs=max(s,maxs);
print(maxs);


    



    
    
    
    


n, p, q, r = [int(i) for i in input().split()]

aa = [int(i) for i in input().split()]

max_from_p = []
m = None

for i in range(n):
    if i == 0:
        m = aa[i] * p
    else:
        if aa[i] * p > m:
            m = aa[i] * p
    max_from_p.append(m)

max_from_pq = []
m = None

for i in range(n):
    if i == 0:
        m = aa[i] * q + max_from_p[i]
    else:
        if aa[i] * q + max_from_p[i] > m:
            m = aa[i] * q + max_from_p[i]
    max_from_pq.append(m)

m = None

for i in range(n):
    if i == 0:
        m = aa[i] * r + max_from_pq[i]
    else:
        if aa[i] * r + max_from_pq[i] > m:
            m = aa[i] * r + max_from_pq[i]

print(m)


max1=[]
max2=[]
max3=[]
N,A,B,C=list(map(int,input().split()))
p=list(map(int,input().split()))
max1.append(-100000000000000000000);
max2.append(-100000000000000000000);
max3.append(-100000000000000000000);
for x in range(1,N+1):
    max1.append(max(max1[x-1],A*p[x-1]));
for x in range(1,N+1):
    max2.append(max(max2[x-1],max1[x]+B*p[x-1]));
for x in range(1,N+1):
    max3.append(max(max3[x-1],max2[x]+C*p[x-1]));
print((max3[-1]));


inf = 10 ** 18
n, p, q, r = map(int, input().split())
a = list(map(int, input().split()))
mx = [-inf] * n
mn = [inf] * n
val2 = [0] * n
mx[0] = a[0]
mn[0] = a[0]
val2[0] = p * a[0] + q * a[0]
for i in range(1, n):
    mn[i] = min(mn[i - 1], a[i])
    mx[i] = max(mx[i - 1], a[i])
    val2[i] = q * a[i] + max(mn[i] * p, mx[i] * p)
val3 = [0] * n
mx2 = [-inf] * n
mx2[0] = val2[0]
val3[0] = val2[0] + r * a[0]
ans = - inf
for i in range(1, n):
    mx2[i] = max(mx2[i - 1], val2[i])
    val3[i] = r * a[i] + mx2[i]
print(max(val3))

n, p, q, r = map(int, input().split())
list1 = list(map(int, input().split()))
pref = [list1[0]]
suf = [list1[-1]]
ans = -3 * 10 ** 18 - 1
if p > 0:
    for i in range(1, n):
        pref.append(max(list1[i], pref[-1]))
else:
    for i in range(1, n):
        pref.append(min(list1[i], pref[-1]))
if r > 0:
    for i in range(n - 2, -1, -1):
        suf.append(max(suf[-1], list1[i]))
else:
    for i in range(n - 2, -1, -1):
        suf.append(min(suf[-1], list1[i]))
for i in range(n):
    ans = max(ans, pref[i] * p + q * list1[i] + suf[n - i -1] * r)
print(ans)

import sys
#=int(input())
#=list(map(int, input().split()))
n, p, q, r = list(map(int, input().split()))
a = list(map(int, input().split()))
minil = [0] * n
minir = [0] * n
maxil = [0] * n
maxir = [0] * n
minil[0] = maxil[0] = a[0]
minir[n - 1] = maxir[n - 1] = a[n - 1]
for i in range(1, n):
    minil[i] = min(minil[i - 1], a[i])
    maxil[i] = max(maxil[i - 1], a[i])
for i in range(n - 2, -1, -1):
    minir[i] = min(minir[i + 1], a[i])
    maxir[i] = max(maxir[i + 1], a[i])
ans = 0
tans = -10**19
for i in range(n):
    ans = q * a[i]
    ans += max(p * minil[i], p * maxil[i])
    ans += max(r * minir[i], r * maxir[i])
    tans = max(tans, ans)
print(tans)


n, p, q, r = map(int, input().split())
a = [int(i) for i in input().split()]
min_suf = [0] * n
max_suf = [0] * n
min_suf[-1] = [n - 1, a[n - 1]]
max_suf[-1] = min_suf[-1]
pqr = [0] * n
qr = [0] * n
rr = [0] * n
rr[-1] = a[-1] * r
for i in range(n - 2, -1, -1):
    if a[i] < min_suf[i + 1][1]:
        min_suf[i] = [i, a[i]]
    else:
        min_suf[i] = min_suf[i + 1]
    if a[i] > max_suf[i + 1][1]:
        max_suf[i] = [i, a[i]]
    else:
        max_suf[i] = max_suf[i + 1]
    if r < 0:
        rr[i] = min_suf[i][1] * r
    else:
        rr[i] = max_suf[i][1] * r
for i in range(n):
    qr[i] = a[i] * q + rr[i]
for i in range(n - 2, -1, -1):
    qr[i] = max(qr[i], qr[i + 1])
ans = a[0] * p + qr[0]
for i in range(n):
    ans = max(a[i] * p + qr[i], ans)
print(ans)



def main():
	n, p, q, r  = [ int(i) for i in input().split() ] 
	L = [ int(i) for i in input().split() ]
	
	
	LR_big = [L[0]]
	LR_small = [L[0]]
	for i in range(1,len(L)):
		LR_big.append( max(L[i], LR_big[-1]) )
		LR_small.append( min(L[i], LR_small[-1]) )
		
	RL_big = [L[-1]]
	RL_small = [L[-1]]
	for i in range( len(L)-2, -1, -1):
		RL_big.append( max(L[i], RL_big[-1] ))
		RL_small.append( min(L[i], RL_small[-1] ))
	
	RL_big = RL_big[::-1]
	RL_small = RL_small[::-1]
	
	"""	
	print(LR_big)
	print(LR_small)
	print(RL_big)
	print(RL_small)
	"""
	
	count = -10**20
	for i in range(len(L)):
		
		count = max(max(LR_small[i]*p, LR_big[i]*p) + L[i]*q + max(RL_small[i]*r, RL_big[i]*r), count)
	
	print(count)
	
main()


def get_ans(n, p, q, r, a):
    maxpre = [-100000000] * n
    minpre = [100000000] * n
    maxsuf = [-100000000] * n
    minsuf = [100000000] * n

    curmax = a[0]
    curmin = a[0]

    for i in range(n):
        if a[i] > curmax:
            curmax = a[i]
        maxpre[i] = curmax

        if a[i] < curmin:
            curmin = a[i]
        minpre[i] = curmin

    curmax = a[n - 1]
    curmin = a[n - 1]

    for i in range(n - 1, -1, -1):
        if a[i] > curmax:
            curmax = a[i]
        maxsuf[i] = curmax

        if a[i] < curmin:
            curmin = a[i]
        minsuf[i] = curmin

    ans = []
    for i in range(n):
        pmas = maxpre if p > 0 else minpre
        rmas = maxsuf if r > 0 else minsuf

        ans.append(pmas[i] * p + a[i] * q + rmas[i] * r)

    return max(ans)

n, p, q, r = tuple(map(int, input().split()))
a = list(map(int, input().split()))
print(get_ans(n, p, q, r, a))




import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n,p,q,r=map(int,input().split())

a=list(map(int,input().split()))

s1=[a[i]*p for i in range(n)]

s2=[]
m=s1[0]
for i in range(n):
    m=max(m,s1[i])
    s2.append(m+a[i]*q)

s3=[]
m=s2[0]
for i in range(n):
    m=max(m,s2[i])
    s3.append(m+a[i]*r)

print(max(s3))

n, p, q ,r = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0, 0, 0] for i in range(n)]
dp[0][0] = p * a[0]
dp[0][1] = dp[0][0] + q * a[0]
dp[0][2] = dp[0][1] + r * a[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][0], p * a[i])
    dp[i][1] = max(dp[i - 1][1], dp[i][0] + q * a[i])
    dp[i][2] = max(dp[i - 1][2], dp[i][1] + r * a[i])
print(dp[n - 1][2])

n,p,q,r=list(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)
            
            


# -------------INPUT---------------------------
n, p, q, r = [int(i) for i in input().split(" ")]
a = input()

b = a.split()

for i in range(n):
    b[i] = int(b[i])

# ---------------------------------------------

dp = [p * b[0]]
for i in range(1, n):
    dp.append(max(dp[i - 1], p * b[i]))
# print(dp)

dq = [dp[0] + q * b[0]]
for i in range(1, n):
    dq.append(max(dq[i - 1], dp[i] + q * b[i]))
# print(dq)

dr = [dq[0] + r * b[0]]
for i in range(1, n):
    dr.append(max(dr[i - 1], dq[i] + r * b[i]))

print(dr[-1])
#  i = 0
# while i < len(a):
#     if a[i] == ' ':
#         i += 1
#     if a[i] == '-':
#         b.append(int(a[i]+a[i+1]))
#         i += 2
#     else:
#         b.append(int(a[i]))
#         i += 1
# print(b)
# num = [p,q,r]
# l = []
# sum = p * b[0] + q * b[0] + r * b[0]
# x = len(b)
# for i in range(x):
#     for j in range(i, x):
#         for k in range(j, x):
#             # print(i,j,k)
#             sum = max(sum, p * b[i] + q * b[j] + r * b[k])
#
# # print(sum)
#
#
# # def indiceb(b):
# #     for i in range(len(b)):
# #         if b[i] == max(b):
#             return i
#
#
# def indices(b):
#     for i in range(len(b)):
#         if b[i] == min(b):
#             return i
#
# if p > 0:
#     sum += max(b) * p
# if p < 0:
#     sum += min(b) * p
#
# if q > 0:
#     sum += max(b[indices(b):]) * q
# if q < 0:
#     sum += min(b) * q
#
# #
# for ii in range(3):
#     if num[ii] >= 0:
#         sum += max(b)*num[ii]
#     if num[ii] < 0:
#         sum += min(b)*num[ii]