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.

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Complete search


Solutions:
(n, p, q, r) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
m_inf = float('-inf')
dp = []
for i in range(n + 1):
	dp.append([m_inf, m_inf, m_inf])
for i in range(1, n + 1):
	dp[i][0] = max(dp[i - 1][0], a[i - 1] * p)
	dp[i][1] = max(dp[i - 1][1], dp[i][0] + a[i - 1] * q)
	dp[i][2] = max(dp[i - 1][2], dp[i][1] + a[i - 1] * r)
print(dp[i][2])


[n, p, q, r] = list(map(int, input().split()))
a = list(map(int, input().split()))
Inf = int(1000000000.0 + 7)
pref_min = [Inf for i in range(n)]
pref_max = [-Inf for i in range(n)]
suf_min = [Inf for i in range(n)]
suf_max = [-Inf for i in range(n)]
pref_min[0] = a[0]
pref_max[0] = a[0]
for i in range(1, n):
	pref_min[i] = min(pref_min[i - 1], a[i])
	pref_max[i] = max(pref_max[i - 1], a[i])
suf_min[n - 1] = a[n - 1]
suf_max[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	suf_min[i] = min(suf_min[i + 1], a[i])
	suf_max[i] = max(suf_max[i + 1], a[i])
res = -int(3e+18 + 7)
for j in range(n):
	x = q * a[j]
	x += max(p * pref_max[j], p * pref_min[j])
	x += max(r * suf_max[j], r * suf_min[j])
	res = max(res, x)
print(res)


(n, p, q, r) = map(int, input().split())
A = list(map(int, input().split()))
(tp, tq, tr) = (-1e+20, -1e+20, -1e+20)
for a in A:
	tp = max(tp, p * a)
	tq = max(tq, tp + q * a)
	tr = max(tr, tq + r * a)
print(tr)


max1 = []
max2 = []
max3 = []
(N, A, B, C) = 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])


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
(pre, suf) = ([p * a[0]], [r * a[n - 1]] * n)
for i in range(1, n):
	pre.append(max(pre[i - 1], p * a[i]))
	suf[n - i - 1] = max(suf[n - i], r * a[n - i - 1])
ans = -float('inf')
for i in range(n):
	ans = max(ans, pre[i] + suf[i] + a[i] * q)
print(ans)


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


(n, p, q, r2) = list(map(int, input().split()))
a = list(map(int, input().split()))
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]
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]
	maxs = max(s, maxs)
print(maxs)


from collections import deque
tmp = list(map(int, input().split()))
(n, p, q, r) = (tmp[0], tmp[1], tmp[2], tmp[3])
a = list(map(int, input().split()))
minLeft = []
minRight = deque()
maxLeft = []
maxRight = deque()
minLeft.append(a[0])
maxLeft.append(a[0])
for i in range(1, n):
	minLeft.append(min(a[i], minLeft[i - 1]))
	maxLeft.append(max(a[i], maxLeft[i - 1]))
minRight.append(a[-1])
maxRight.append(a[-1])
for i in range(n - 2, -1, -1):
	minRight.appendleft(min(a[i], minRight[0]))
	maxRight.appendleft(max(a[i], maxRight[0]))
s = q * a[0]
if p <= 0:
	s += p * minLeft[0]
else:
	s += p * maxLeft[0]
if r <= 0:
	s += r * minRight[0]
else:
	s += r * maxRight[0]
for i in range(1, n):
	tmp = q * a[i]
	if p <= 0:
		tmp += p * minLeft[i]
	else:
		tmp += p * maxLeft[i]
	if r <= 0:
		tmp += r * minRight[i]
	else:
		tmp += r * maxRight[i]
	if tmp > s:
		s = tmp
print(s)


class CodeforcesTask855BSolution:

	def __init__(self):
		self.result = ''
		self.n_p_q_r = []
		self.a = []

	def read_input(self):
		self.n_p_q_r = [int(x) for x in input().split(' ')]
		self.a = [int(x) for x in input().split(' ')]

	def process_task(self):
		dp = [[0] * self.n_p_q_r[0] for x in range(3)]
		for x in range(3):
			dp[x][0] = self.a[0] * self.n_p_q_r[1 + x]
			if x > 0:
				dp[x][0] += dp[x - 1][0]
			for y in range(1, self.n_p_q_r[0]):
				if not x:
					dp[x][y] = max(dp[x][y - 1], self.a[y] * self.n_p_q_r[1 + x])
				else:
					dp[x][y] = max(dp[x][y - 1], self.a[y] * self.n_p_q_r[1 + x] + dp[x - 1][y])
		self.result = str(dp[2][-1])

	def get_result(self):
		return self.result
Solution = CodeforcesTask855BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, p, q, r) = input().split()
n = int(n)
p = int(p)
q = int(q)
r = int(r)
ls = list(map(int, input().split()))
ans = -9223372036854775807
ls1 = [None] * n
ls2 = [None] * n
ls3 = [None] * n
ls5 = [None] * n
ls4 = [[None] * n for i in range(3)]
for i in range(0, n):
	ls1[i] = p * ls[i]
	ls2[i] = r * ls[i]
	ls5[i] = q * ls[i]
ls3[n - 1] = n - 1
for i in range(0, n - 1):
	if ls2[n - i - 2] > ls2[n - i - 2 + 1]:
		ls3[n - i - 2] = n - i - 2
	else:
		ls3[n - i - 2] = ls3[n - i - 2 + 1]
ls4[0][0] = ls1[0]
ls4[1][0] = ls5[0] + ls1[0]
ls4[2][0] = ls2[ls3[0]]
ans = max(ans, ls4[1][0] + ls4[2][0])
for i in range(1, n):
	ls4[0][i] = max(ls4[0][i - 1], ls1[i])
	ls4[1][i] = max(ls4[1][i - 1], ls4[0][i] + ls5[i])
	ls4[2][i] = ls2[ls3[i]]
	ans = max(ans, ls4[1][i] + ls4[2][i])
print(ans)


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


def fun(n, p, q, r, li):
	sfmax = [0 for i in range(n)]
	sfmax[n - 1] = r * li[n - 1]
	for j in range(n - 2, -1, -1):
		sfmax[j] = max(sfmax[j + 1], r * li[j])
	ans = -float('inf')
	pmax = []
	pmax.append(p * li[0])
	for i in range(1, n):
		pmax.append(max(pmax[j - 1], p * li[i]))
	for j in range(0, n):
		ans = max(ans, pmax[j] + li[j] * q + sfmax[j])
	return ans
(n, p, q, r) = list(map(lambda x: int(x), input().split()))
li = list(map(lambda x: int(x), input().split()))
print(fun(n, p, q, r, li))


read_int = lambda string: list(map(int, string.split()))

def max_until_i(k, arr, v):
	x = [None] * len(arr)
	x[0] = k * arr[0] + v[0]
	for i in range(1, len(arr)):
		x[i] = max(x[i - 1], k * arr[i] + v[i])
	return x

def main():
	(n, p, q, r) = read_int(input())
	arr = read_int(input())
	x = max_until_i(p, arr, [0] * len(arr))
	y = max_until_i(q, arr, x)
	z = max_until_i(r, arr, y)
	print(z[-1])
main()


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
mxLeft = [a[0]]
mnLeft = [a[0]]
for i in range(1, n):
	mxLeft.append(max(mxLeft[-1], a[i]))
	mnLeft.append(min(mnLeft[-1], a[i]))
mxRight = [a[n - 1]]
mnRight = [a[n - 1]]
for i in range(n - 2, -1, -1):
	mxRight.append(max(mxRight[-1], a[i]))
	mnRight.append(min(mnRight[-1], a[i]))
ans = []
for i in range(n):
	ans.append(q * a[i])
	if p < 0:
		ans[-1] += mnLeft[i] * p
	else:
		ans[-1] += mxLeft[i] * p
	if r < 0:
		ans[-1] += mnRight[n - i - 1] * r
	else:
		ans[-1] += mxRight[n - i - 1] * r
print(max(ans))


(n, a, b, c) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
dp = [[0] * n for i in range(3)]
dp[0][0] = a * l[0]
dp[1][0] = dp[0][0] + b * l[0]
dp[2][0] = dp[1][0] + c * l[0]
for i in range(1, n):
	dp[0][i] = max(dp[0][i - 1], a * l[i])
	dp[1][i] = max(dp[1][i - 1], dp[0][i] + b * l[i])
	dp[2][i] = max(dp[2][i - 1], dp[1][i] + c * l[i])
print(dp[2][n - 1])


(N, P, Q, R) = map(int, input().split())
arr = list(map(int, input().split()))
l = float('-inf')
Pmax = [0] * N
Pmax[0] = P * arr[0]
for i in range(1, N):
	Pmax[i] = max(Pmax[i - 1], P * arr[i])
Smax = [0] * N
Smax[N - 1] = R * arr[N - 1]
for j in range(N - 2, -1, -1):
	Smax[j] = max(R * arr[j], Smax[j + 1])
for i in range(0, N):
	l = max(l, Pmax[i] + Q * arr[i] + Smax[i])
print(l)


x = list(map(int, input().split()))
n = x[0]
x[0] = 0
data = list(map(int, input().split()))
ans = [-10 ** 19] * 4
ans[0] = 0
for i in data:
	for j in range(1, 4):
		ans[j] = max(ans[j], ans[j - 1] + x[j] * i)
print(ans[3])


(n, x, y, z) = map(int, input().split())
l = [int(x) for x in input().split()]
a = -1e+21
b = -1e+21
c = -1e+21
for i in range(n):
	temp = l[i]
	a = max(a, x * temp)
	b = max(b, a + y * temp)
	c = max(c, b + z * temp)
print(c)


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split(' ')))
dpr = [-10 ** 18 for i in range(n)]
dpr[-1] = r * a[-1]
for k in reversed(range(n - 1)):
	dpr[k] = max(dpr[k + 1], r * a[k])
dpqr = [-10 ** 18 for i in range(n)]
dpqr[-1] = (q + r) * a[-1]
for k in reversed(range(n - 1)):
	dpqr[k] = max(dpqr[k + 1], q * a[k] + dpr[k])
ans = (p + q + r) * a[-1]
for k in reversed(range(n)):
	ans = max(p * a[k] + dpqr[k], ans)
print(ans)


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


inp = input().split()
n = int(inp[0])
p = int(inp[1])
q = int(inp[2])
r = int(inp[3])
del inp
del n
a = input().split()
mas_1 = list()
mas_2 = list()
mas_3 = list()
max = int(a[0]) * p
for i in a:
	if int(i) * p > max:
		max = int(i) * p
	mas_1.append(max)
max = mas_1[0] + int(a[0]) * q
for i in range(len(a)):
	if mas_1[i] + int(a[i]) * q > max:
		max = mas_1[i] + int(a[i]) * q
	mas_2.append(max)
max = mas_2[0] + int(a[0]) * r
for i in range(len(a)):
	if mas_2[i] + int(a[i]) * r > max:
		max = mas_2[i] + int(a[i]) * r
	mas_3.append(max)
print(mas_3[len(mas_3) - 1])


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

def dp():
	rec = [[0 for j in range(3)] for i in range(n)]
	rec[0][0] = p * t[0]
	rec[0][1] = rec[0][0] + q * t[0]
	rec[0][2] = rec[0][1] + r * t[0]
	for i in range(1, n):
		rec[i][0] = max(rec[i - 1][0], p * t[i])
		rec[i][1] = max(rec[i - 1][1], rec[i][0] + q * t[i])
		rec[i][2] = max(rec[i - 1][2], rec[i][1] + r * t[i])
	return rec[n - 1][2]
print(dp())


(max_integer, map1) = (max, map)
(n, p, q, r) = map1(int, input().strip().split())
list1 = list(map1(int, input().strip().split()))
(prefix_max, suffix_max, result) = ([0] * n, [0] * n, float('-inf'))
prefix_max[0] = p * list1[0]
for i in range(1, n):
	prefix_max[i] = max_integer(prefix_max[i - 1], p * list1[i])
suffix_max[n - 1] = r * list1[n - 1]
for i in range(n - 2, -1, -1):
	suffix_max[i] = max_integer(suffix_max[i + 1], r * list1[i])
for i in range(n):
	result = max_integer(result, prefix_max[i] + q * list1[i] + suffix_max[i])
print(f'{result}')


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
b = a[::-1]
ma = [0] * n
mb = [0] * n
Ma = [0] * n
Mb = [0] * n
ma[0] = Ma[0] = a[0]
mb[0] = Mb[0] = b[0]
for i in range(1, n):
	ma[i] = min(ma[i - 1], a[i])
	mb[i] = min(mb[i - 1], b[i])
	Ma[i] = max(Ma[i - 1], a[i])
	Mb[i] = max(Mb[i - 1], b[i])
ans = (p + q + r) * a[0]
for j in range(n):
	z = max(ma[j] * p, Ma[j] * p) + q * a[j] + max(mb[n - 1 - j] * r, Mb[n - 1 - j] * r)
	ans = max(ans, z)
print(ans)


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = p * a[0] + q * a[0] + r * a[0]
b = [0] * n
c = [0] * n
d = [0] * n
e = [0] * n
b[0] = a[0]
c[0] = a[0]
for i in range(1, n):
	b[i] = max(b[i - 1], a[i])
	c[i] = min(c[i - 1], a[i])
d[n - 1] = a[n - 1]
e[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	d[i] = max(d[i + 1], a[i])
	e[i] = min(e[i + 1], a[i])
for j in range(n):
	v = a[j] * q + max(b[j] * p, c[j] * p) + max(d[j] * r, e[j] * r)
	ans = max(ans, v)
print(ans)


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


(n, p, q, r) = map(int, input().split())
li = list(map(int, input().split()))
a = b = c = -10 ** 20
for i in range(len(li)):
	a = max(a, li[i] * p)
	b = max(b, a + li[i] * q)
	c = max(c, b + li[i] * r)
print(c)


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


(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)


maxi = ks = -554564764545467545566666634534554
l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
(r_list, p_list) = ([0] * len(l1), [0] * len(l1))
r_list[-1] = l[3] * l1[-1]
p_list[0] = l1[0] * l[1]
for i in range(len(l1) - 2, -1, -1):
	r_list[i] = max(r_list[i + 1], l1[i] * l[3])
for i in range(1, len(l1)):
	p_list[i] = max(p_list[i - 1], l[1] * l1[i])
for i in range(len(l1)):
	ks = r_list[i] + p_list[i] + l[2] * l1[i]
	maxi = max(maxi, ks)
print(maxi)


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]
	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()


(n, p, q, r) = map(int, input().split())
lst = []
for x in input().split():
	lst.append(int(x))
a = -10 ** 20
b = -10 ** 20
c = -10 ** 20
for x in lst:
	a = max(a, x * p)
	b = max(b, a + x * q)
	c = max(c, b + x * r)
print(c)


vals = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
dp = [[0 for i in range(vals[0])] for i in range(3)]
n = vals[0]
dp[-1][-1] = vals[3] * arr[-1]
for i in range(n - 2, -1, -1):
	dp[-1][i] = max(dp[-1][i + 1], arr[i] * vals[3])
for i in range(1, -1, -1):
	dp[i][-1] = arr[-1] * vals[i + 1] + dp[i + 1][-1]
	for j in range(n - 2, -1, -1):
		dp[i][j] = max(dp[i][j + 1], arr[j] * vals[i + 1] + dp[i + 1][j])
print(dp[0][0])


(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)


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


import sys
(length, p, q, r) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
inp = [int(x) for x in sys.stdin.readline().strip().split(' ')]
my_dict = dict()
my_dict['p'] = -1 * float('inf')
my_dict['q'] = -1 * float('inf')
my_dict['r'] = -1 * float('inf')
for x in inp:
	my_dict['p'] = max(my_dict['p'], p * x)
	my_dict['q'] = max(my_dict['q'], q * x + my_dict['p'])
	my_dict['r'] = max(my_dict['r'], r * x + my_dict['q'])
print(my_dict['r'])


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
(x, y, z) = (-float('inf'), -float('inf'), -float('inf'))
for i in range(n):
	z = max(z, p * a[i])
	y = max(y, z + q * a[i])
	x = max(x, y + r * a[i])
print(x)


import math
(n, p, q, r) = (int(x) for x in input().split())
arr_n = [int(x) for x in input().split()]
ans = -math.inf
p_max = [0] * n
s_max = [0] * n
p_max[0] = p * arr_n[0]
s_max[n - 1] = r * arr_n[n - 1]
for i in range(1, n):
	p_max[i] = max(p_max[i - 1], p * arr_n[i])
for i in range(n - 2, -1, -1):
	s_max[i] = max(s_max[i + 1], r * arr_n[i])
for i in range(n):
	ans = max(ans, p_max[i] + q * arr_n[i] + s_max[i])
print(ans)


def list_input():
	return list(map(int, input().split()))

def map_input():
	return 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])


(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)


def Dumbledore2(n, p, q, r, arr):
	dp = [None] * 100000
	dp[0] = p * arr[0]
	for i in range(1, n):
		dp[i] = max(dp[i - 1], arr[i] * p)
	dp1 = [None] * 100000
	dp1[0] = dp[0] + q * arr[0]
	for i in range(1, n):
		dp1[i] = max(dp1[i - 1], arr[i] * q + dp[i])
	dp2 = [None] * 100000
	dp2[0] = dp1[0] + r * arr[0]
	for i in range(1, n):
		dp2[i] = max(dp2[i - 1], arr[i] * r + dp1[i])
	print(dp2[n - 1])
(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
Dumbledore2(n, p, q, r, arr)


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
pqr = [p, q, r]
mat = [[0 for j in range(n)] for i in range(3)]
for i in range(3):
	for j in range(n):
		if i == 0:
			if j == 0:
				mat[i][j] = pqr[i] * a[j]
			else:
				mat[i][j] = max(mat[i][j - 1], pqr[i] * a[j])
		elif i == 1 or i == 2:
			if j == 0:
				mat[i][j] = mat[i - 1][j] + pqr[i] * a[j]
			else:
				mat[i][j] = max(mat[i][j - 1], mat[i - 1][j] + pqr[i] * a[j])
print(mat[2][n - 1])


import sys
(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
prefixmax = [0 for i in range(0, n)]
suffixmax = [0 for i in range(0, n)]
suffixmax[n - 1] = r * a[n - 1]
prefixmax[0] = p * a[0]
for i in range(1, n):
	prefixmax[i] = max(prefixmax[i - 1], p * a[i])
for i in range(n - 2, -1, -1):
	suffixmax[i] = max(suffixmax[i + 1], r * a[i])
ans = -1 * sys.maxsize * 10 ** 15
for j in range(0, n):
	x = 0
	x += prefixmax[j] + suffixmax[j] + q * a[j]
	ans = max(x, ans)
print(ans)


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


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


(n, p, q, r) = map(int, input().split())
arr = [int(i) for i in input().split()]
siz = len(arr)
pre_max = [0] * siz
suf_max = [0] * siz
pre_max[0] = p * arr[0]
suf_max[n - 1] = r * arr[n - 1]
for i in range(1, len(arr)):
	pre_max[i] = max(pre_max[i - 1], p * arr[i])
for i in range(len(arr) - 2, -1, -1):
	suf_max[i] = max(suf_max[i + 1], r * arr[i])
ans = float('-inf')
for i in range(len(arr)):
	x = pre_max[i] + q * arr[i] + suf_max[i]
	ans = max(ans, x)
print(ans)


(nn, p, q, r) = map(int, input().split())
ar = list(map(int, input().split()))
max_l = [ar[0]]
for i in range(1, nn):
	max_l.append(max(max_l[-1], ar[i]))
min_l = [ar[0]]
for i in range(1, nn):
	min_l.append(min(min_l[-1], ar[i]))
max_r = [0] * nn
max_r[-1] = ar[-1]
for i in range(nn - 2, -1, -1):
	max_r[i] = max(max_r[i + 1], ar[i])
min_r = [0] * nn
min_r[-1] = ar[-1]
for i in range(nn - 2, -1, -1):
	min_r[i] = min(min_r[i + 1], ar[i])
ans = -3 * 10 ** 19
for i in range(0, nn):
	t = q * ar[i]
	t += p * (min_l[i] if p < 0 else max_l[i])
	t += r * (min_r[i] if r < 0 else max_r[i])
	ans = max(ans, t)
print(ans)


(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))
elif 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)


(n, p, q, r) = map(int, input().split())
alist = list(map(int, input().split()))
(a, b, c) = (-8e+18, -8e+18, -8e+18)
for i in range(n):
	a = max(a, alist[i] * p)
	b = max(b, a + alist[i] * q)
	c = max(c, b + alist[i] * r)
print(c)


(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]))
dq = [dp[0] + q * b[0]]
for i in range(1, n):
	dq.append(max(dq[i - 1], dp[i] + q * b[i]))
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])


(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
	elif 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]
	elif 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]
	elif aa[i] * r + max_from_pq[i] > m:
		m = aa[i] * r + max_from_pq[i]
print(m)


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


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

def solve():
	dp = [float('-inf')] * n
	dp[0] = B[0] * A[0]
	for i in range(1, n):
		dp[i] = max(B[0] * A[i], dp[i - 1])
	for j in range(1, 3):
		new_dp = [float('-inf')] * n
		new_dp[0] = A[0] * B[j] + dp[0]
		for i in range(1, n):
			new_dp[i] = max(new_dp[i - 1], A[i] * B[j] + dp[i])
		dp = new_dp
	return max(dp)
print(solve())


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


I = lambda : map(int, input().rstrip().split())
(n, p, q, r) = I()
a = list(I())
pp = -1e+20
pq = -1e+20
pr = -1e+20
for x in a:
	pp = max(pp, p * x)
	pq = max(pq, pp + q * x)
	pr = max(pr, pq + r * x)
print(pr)


import sys
(n, p, q, r) = map(int, input().split())
lst = list(map(int, input().split()))
suffix_max = [0 for _ in range(n)]
suffix_max[n - 1] = r * lst[n - 1]
for i in range(n - 2, -1, -1):
	suffix_max[i] = max(suffix_max[i + 1], lst[i] * r)
left = lst[0] * p
res = -999999999999999999999999999999
for i in range(n):
	mid = lst[i] * q
	left = max(left, lst[i] * p)
	right = suffix_max[i]
	res = max(res, left + right + mid)
print(res)


import sys
input = sys.stdin.buffer.readline

def solution():
	(n, p, q, r) = map(int, input().split())
	l = list(map(int, input().split()))
	np = -2e+19
	nq = -2e+19
	nr = -2e+19
	for i in range(n):
		np = max(np, p * l[i])
		nq = max(nq, np + q * l[i])
		nr = max(nr, nq + r * l[i])
	print(nr)
solution()


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) = list(map(int, input().split()))
a = list(map(int, input().split()))
dp1 = [0] * n
for i in range(n):
	if i == 0:
		dp1[i] = p * a[i]
	else:
		dp1[i] = max(dp1[i - 1], p * a[i])
dp2 = [0] * n
for i in range(n):
	if i == 0:
		dp2[i] = p * a[i] + q * a[i]
	else:
		dp2[i] = max(q * a[i] + dp1[i], dp2[i - 1])
ans = -float('inf')
for i in range(n):
	ans = max(ans, r * a[i] + dp2[i])
print(ans)


(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) = map(int, input().split())
(*a,) = map(int, input().split())
dp = [[p * a[0], (p + q) * a[0], (p + q + r) * a[0]] for i in range(n)]
for i in range(1, n):
	dp[i][0] = max(dp[i - 1][0], p * a[i])
for i in range(1, n):
	dp[i][1] = max(dp[i - 1][1], dp[i][0] + q * a[i])
for i in range(1, n):
	dp[i][2] = max(dp[i - 1][2], dp[i][1] + r * a[i])
print(dp[n - 1][2])


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)


(n, p, q, r) = map(int, input().split())
li = []
li = list(map(int, input().split()))
for i in range(len(li)):
	if i == 0:
		x = li[i] * p
		y = li[i] * q + x
		z = li[i] * r + y
	else:
		x = max(li[i] * p, x)
		y = max(x + li[i] * q, y)
		z = max(y + li[i] * r, z)
print(z)


(n, p, q, r) = tuple((int(i) for i in input().split(' ')))
data = [int(i) for i in input().split(' ')]
prefix = []
suffix = []
prefix.append(data[0] * p)
suffix.append(data[n - 1] * r)
len_d = len(data)
maxnum = prefix[0]
for i in range(1, len_d):
	if maxnum < data[i] * p:
		maxnum = data[i] * p
	prefix.append(maxnum)
maxnum = suffix[0]
for i in range(len_d - 2, -1, -1):
	if maxnum < data[i] * r:
		maxnum = data[i] * r
	suffix.insert(0, maxnum)
maxnum = prefix[0] + q * data[0] + suffix[0]
for i in range(0, len_d):
	tmp = prefix[i] + q * data[i] + suffix[i]
	if maxnum < tmp:
		maxnum = tmp
print(maxnum)


(n, p, q, r) = map(int, input().split())
v = list(map(int, input().split()))
d = [0] * n
for i in range(n - 1, -1, -1):
	if i == n - 1:
		d[i] = r * v[i]
	elif d[i + 1] > r * v[i]:
		d[i] = d[i + 1]
	else:
		d[i] = r * v[i]
(now, ans) = (0, -3 * 10 ** 18)
for i in range(n):
	if i == 0:
		now = p * v[i]
	elif now < p * v[i]:
		now = p * v[i]
	ans = max(ans, now + q * v[i] + d[i])
print(ans)


(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
n = len(arr)
if n == 1:
	print(arr[0] * (p + q + r))
else:
	pref = [arr[0]]
	if p > 0:
		for i in range(1, n):
			pref.append(max(pref[-1], arr[i]))
	else:
		for i in range(1, n):
			pref.append(min(pref[-1], arr[i]))
	suff = [arr[-1]]
	if r > 0:
		for i in range(n - 2, -1, -1):
			suff.append(max(suff[-1], arr[i]))
	else:
		for i in range(n - 2, -1, -1):
			suff.append(min(suff[-1], arr[i]))
	suff = suff[::-1]
	ans = float('-inf')
	for i in range(n):
		ans = max(ans, p * pref[i] + q * arr[i] + r * suff[i])
	print(ans)


(n, p, q, r) = list(map(int, input().split()))
alist = list(map(int, input().split()))
first = [alist[0]]
if p < 0:
	for i in range(1, n):
		first.append(min(alist[i], first[i - 1]))
else:
	for i in range(1, n):
		first.append(max(alist[i], first[i - 1]))
last = [alist[n - 1]]
if r < 0:
	for i in range(0, n - 1):
		last.insert(0, min(alist[n - 2 - i], last[0]))
else:
	for i in range(0, n - 1):
		last.insert(0, max(alist[n - 2 - i], last[0]))
ans = -9999999999999999999999999999
itrans = 0
for i in range(0, n):
	itrans = p * first[i] + q * alist[i] + r * last[i]
	if itrans > ans:
		ans = itrans
print(ans)


(n, p, q, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
prefix = [None for _ in range(n)]
suffix = [None for _ in range(n)]
p_compare = max if p > 0 else min
r_compare = max if r > 0 else min
for i in range(n):
	if i == 0:
		prefix[i] = a[i]
	else:
		prefix[i] = p_compare(a[i], prefix[i - 1])
for i in range(n - 1, -1, -1):
	if i == n - 1:
		suffix[i] = a[i]
	else:
		suffix[i] = r_compare(a[i], suffix[i + 1])
optimum = None
for j in range(n):
	s = a[j] * q
	s += prefix[j] * p
	s += suffix[j] * r
	if optimum is None:
		optimum = s
	else:
		optimum = max(optimum, s)
print(optimum)


import sys
import bisect
import heapq
import math
from functools import lru_cache
from collections import defaultdict, Counter
input = sys.stdin.readline
I = lambda : int(input())
S = lambda : input()
L = lambda : list(map(int, input().split()))

def solution(n, p, q, r):
	a = L()
	temp1 = float('inf')
	temp2 = float('-inf')
	left_min = []
	left_max = []
	right_min = []
	right_max = []
	for i in a:
		temp1 = min(i, temp1)
		temp2 = max(i, temp2)
		left_min.append(temp1)
		left_max.append(temp2)
	temp1 = float('inf')
	temp2 = float('-inf')
	for i in a[::-1]:
		temp1 = min(i, temp1)
		temp2 = max(i, temp2)
		right_min.append(temp1)
		right_max.append(temp2)
	right_min.reverse()
	right_max.reverse()
	res = float('-inf')
	n = len(a)
	for i in range(n):
		x = max(p * left_max[i], p * left_min[i])
		y = max(r * right_max[i], r * right_min[i])
		z = q * a[i]
		res = max(res, x + y + z)
	print(res)
(n, p, q, r) = L()
solution(n, p, q, r)


import sys
(n, p, q, r) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))

def find_pref_sum(array):
	maxm = -2 ** 63
	pref_sum = [0] * n
	for i in range(0, n):
		pref_sum[i] = max(maxm, array[i] * p)
		maxm = max(maxm, array[i] * p)
	return pref_sum

def find_suff_sum(array):
	maxm = -2 ** 63
	suff_sum = [0] * n
	for j in reversed(range(n)):
		suff_sum[j] = max(maxm, array[j] * r)
		maxm = max(maxm, array[j] * r)
	return suff_sum
pref_sum = find_pref_sum(arr)
suff_sum = find_suff_sum(arr)

def find_max_expression(p, q, r, arr):
	max_exp = -2 ** 63
	for i in range(0, n):
		max_exp = max(max_exp, max(p * arr[i], pref_sum[i]) + arr[i] * q + max(r * arr[i], suff_sum[i]))
	return max_exp
max_expression_val = find_max_expression(p, q, r, arr)
print(max_expression_val)


a = list(map(int, input().split()))
arr = list(map(int, input().split()))
c = a[1:]
pmax = [float('-inf') for i in range(a[0])]
smax = [float('-inf') for i in range(a[0])]
pmax[0] = c[0] * arr[0]
v = float('-inf')
for i in range(a[0]):
	pmax[i] = max(pmax[i - 1], c[0] * arr[i])
smax[a[0] - 1] = c[2] * arr[a[0] - 1]
for i in range(a[0] - 2, -1, -1):
	smax[i] = max(smax[i + 1], c[2] * arr[i])
for i in range(a[0]):
	v = max(v, pmax[i] + c[1] * arr[i] + smax[i])
print(v)


import copy
N = input()
N = list(map(int, N.split(' ')))
Arr = input()
Arr = list(map(int, Arr.split(' ')))
p = N[1]
q = N[2]
r = N[3]
prefixmax = [i * p for i in Arr]
suffixmax = [i * r for i in Arr]
for i in range(1, N[0]):
	if p * Arr[i] > prefixmax[i - 1]:
		prefixmax[i] = p * Arr[i]
	else:
		prefixmax[i] = prefixmax[i - 1]
for i in range(N[0] - 2, -1, -1):
	if r * Arr[i] > suffixmax[i + 1]:
		suffixmax[i] = r * Arr[i]
	else:
		suffixmax[i] = suffixmax[i + 1]
MAX = list()
for i in range(0, len(Arr)):
	MAX.append(prefixmax[i] + q * Arr[i] + suffixmax[i])
print(max(MAX))


(n, p, q, r) = map(int, input().split())
List = [int(x) for x in input().split()]
MaxPre = []
MaxSuf = []
MinPre = []
MinSuf = []
Max = List[0]
Min = List[0]
for i in range(n):
	Max = max(Max, List[i])
	Min = min(Min, List[i])
	MaxPre.append(Max)
	MinPre.append(Min)
Max = List[-1]
Min = List[-1]
for i in range(n - 1, -1, -1):
	Max = max(Max, List[i])
	Min = min(Min, List[i])
	MaxSuf.append(Max)
	MinSuf.append(Min)
MaxSuf.reverse()
MinSuf.reverse()
Ans = -1000000000000000000000000000000000000000000000
for i in range(n):
	cal = q * List[i]
	if p < 0:
		cal += p * MinPre[i]
	else:
		cal += p * MaxPre[i]
	if r < 0:
		cal += r * MinSuf[i]
	else:
		cal += r * MaxSuf[i]
	Ans = max(Ans, cal)
print(Ans)


(n, p, q, r) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if len(a) == 0:
	print(0)
pmax = []
pmax.append(p * a[0])
for i in range(1, n):
	pmax.append(max(pmax[i - 1], a[i] * p))
smax = a[n - 1] * r
res = pmax[n - 1] + a[n - 1] * q + smax
for i in range(n - 2, -1, -1):
	smax = max(smax, a[i] * r)
	res = max(pmax[i] + a[i] * q + smax, res)
print(res)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
import bisect
(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
v1 = [0] * n
v2 = [0] * n
v1[0] = v2[0] = arr[0]
for i in range(1, n):
	v1[i] = min(arr[i], v1[i - 1])
	v2[i] = max(arr[i], v2[i - 1])
v3 = [0] * n
v4 = [0] * n
v3[-1] = v4[-1] = arr[-1]
for i in range(n - 2, -1, -1):
	v3[i] = min(arr[i], v3[i + 1])
	v4[i] = max(arr[i], v4[i + 1])
ans = -3 * 10 ** 18
for i in range(n):
	val = q * arr[i]
	if p <= 0:
		val += p * v1[i]
	else:
		val += p * v2[i]
	if r <= 0:
		val += r * v3[i]
	else:
		val += r * v4[i]
	ans = max(ans, val)
print(ans)


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
(t1, t2, t3) = (-10 ** 20, -10 ** 20, -10 ** 20)
for i in range(n):
	t1 = max(t1, p * a[i])
	t2 = max(t2, t1 + q * a[i])
	t3 = max(t3, t2 + r * a[i])
print(t3)


import math
ans = -math.inf
(n, p, q, r) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
prefixMax = [0 for i in range(n)]
suffixMax = [0 for i in range(n)]
prefixMax[0] = p * arr[0]
suffixMax[n - 1] = r * arr[n - 1]
for i in range(1, n):
	prefixMax[i] = max(prefixMax[i - 1], p * arr[i])
for i in range(n - 2, -1, -1):
	suffixMax[i] = max(suffixMax[i + 1], r * arr[i])
for i in range(n):
	ans = max(ans, prefixMax[i] + q * arr[i] + suffixMax[i])
print(ans)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	(n, p, q, r) = lst()
	a = lst()
	NI = float('-inf')
	dp1 = [NI] * n
	dp2 = [NI] * n
	dp3 = [NI] * n
	for i in range(n):
		if i == 0:
			dp1[i] = a[i] * p
		else:
			dp1[i] = max(dp1[i - 1], a[i] * p)
	for i in range(n):
		if i == 0:
			dp2[i] = dp1[i] + a[i] * q
		dp2[i] = max(dp1[i] + q * a[i], dp2[i - 1])
	for i in range(n):
		if i == 0:
			dp3[i] = dp2[i] + r * a[0]
		else:
			dp3[i] = max(dp3[i - 1], dp2[i] + a[i] * r)
	print(max(dp3))


def maxSum(arr, p, q, r):
	premax = -214748364800000000000000000000000000000
	postmax = -2147483648000000000000000000000000000000
	maxx = -214748364800000000000000000000000000000000000
	pre = []
	post = []
	for i in arr:
		premax = max(p * i, premax)
		pre.append(premax)
	for j in range(len(arr) - 1, -1, -1):
		postmax = max(r * arr[j], postmax)
		post.append(postmax)
	for i in range(0, len(arr)):
		summ = 0
		summ = q * arr[i] + pre[i] + post[len(arr) - i - 1]
		maxx = max(summ, maxx)
	return maxx
(n, p, q, r) = [int(v) for v in input().split()]
arr = [int(v) for v in input().split()][:n]
print(maxSum(arr, p, q, r))


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
px = qx = rx = -1e+21
for i in range(n):
	px = max(px, p * a[i])
	qx = max(qx, px + q * a[i])
	rx = max(rx, qx + r * a[i])
print(rx)


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) = map(int, input().split())
arr = [int(i) for i in input().split()]
parr = [arr[0] * p]
for i in range(1, len(arr)):
	val = max(arr[i] * p, parr[i - 1])
	parr.append(val)
qarr = [arr[0] * q + p * arr[0]]
for i in range(1, len(arr)):
	val = max(qarr[i - 1], arr[i] * q + parr[i])
	qarr.append(val)
rarr = [arr[0] * q + p * arr[0] + r * arr[0]]
for i in range(1, len(arr)):
	val = max(rarr[i - 1], r * arr[i] + qarr[i])
	rarr.append(val)
print(rarr[-1])


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
total = p + q + r
if n == 1:
	print(total * a[0])
	exit()
if p > 0 and q > 0 and (r > 0):
	print(total * max(a))
	exit()
if p < 0 and q < 0 and (r < 0):
	print(total * min(a))
	exit()
p_vals = [None] * n
p_vals[0] = p * a[0]
for i in range(1, n):
	p_vals[i] = max(p_vals[i - 1], p * a[i])
pq_vals = [None] * n
pq_vals[0] = p_vals[0] + q * a[0]
for i in range(1, n):
	pq_vals[i] = max(pq_vals[i - 1], p_vals[i] + q * a[i])
ans = pq_vals[0] + r * a[0]
for i in range(1, n):
	ans = max(ans, pq_vals[i] + r * a[i])
print(ans)


(n, p, q, r) = map(int, input().split())
ar = list(map(int, input().split()))
su = r * ar[-1]
suf = [0] * n
for i in range(n - 1, -1, -1):
	su = suf[i] = max(r * ar[i], su)
pr = p * ar[0]
ans = -1111111111111111111111111111
for i in range(n):
	pr = max(pr, p * ar[i])
	ans = max(ans, pr + q * ar[i] + suf[i])
print(ans)


(n, p, q, r) = map(int, input().split())
a = [int(i) for i in input().split()]
pp = float('-inf')
qq = float('-inf')
rr = float('-inf')
for x in a:
	pp = max(pp, x * p)
	qq = max(qq, pp + x * q)
	rr = max(rr, qq + x * r)
print(rr)


import sys
(mod, MOD) = (1000000007, 998244353)
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, p, q, r) = get_ints()
Arr = get_array()
dp = [[0 for i in range(n)] for j in range(3)]
dp[0][0] = p * Arr[0]
dp[1][0] = (p + q) * Arr[0]
dp[2][0] = (p + q + r) * Arr[0]
for i in range(1, n):
	dp[0][i] = max(dp[0][i - 1], p * Arr[i])
	dp[1][i] = max(dp[1][i - 1], dp[0][i] + q * Arr[i])
	dp[2][i] = max(dp[2][i - 1], dp[1][i] + r * Arr[i])
print(dp[2][n - 1])


a = input().split()
n = int(a[0])
(p, q, r) = (int(a[1]), int(a[2]), int(a[3]))
ar = [p, q, r]
array = input().split()
fin = []
for i in array:
	fin.append(int(i))
dp = [[0 for x in range(len(array))] for y in range(3)]
i = 0
while i < len(array):
	j = 0
	while j < 3:
		if i == 0:
			if j == 0:
				dp[j][i] = ar[j] * fin[0]
			else:
				dp[j][i] = dp[j - 1][i] + ar[j] * fin[0]
		elif j == 0:
			dp[j][i] = max(ar[j] * fin[i], dp[j][i - 1])
		else:
			dp[j][i] = max(dp[j][i - 1], dp[j - 1][i] + ar[j] * fin[i])
		j += 1
	i += 1
print(dp[2][-1])


def main():
	import sys
	input = sys.stdin.readline
	(n, p, q, r) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [[-10 ** 27] * 3 for _ in range(n)]
	dp[0][0] = p * arr[0]
	dp[0][1] = dp[0][0] + q * arr[0]
	dp[0][2] = dp[0][1] + r * arr[0]
	ans = dp[0][2]
	for i in range(1, n):
		dp[i][0] = max(dp[i - 1][0], p * arr[i])
		dp[i][1] = max(dp[i - 1][1], dp[i][0] + q * arr[i])
		dp[i][2] = max(dp[i - 1][2], dp[i][1] + r * arr[i])
		ans = max(ans, dp[i][2])
	print(ans)
	return 0
main()


Arr = list(map(int, input().split()))
p = Arr[1]
q = Arr[2]
r = Arr[3]
org_arr = list(map(int, input().split()))
precal_premax = [-1] * len(org_arr)
precal_suffmax = [-1] * len(org_arr)
max_ele = p * org_arr[0]
for i in range(len(org_arr)):
	if max_ele < p * org_arr[i]:
		max_ele = org_arr[i] * p
	precal_premax[i] = max_ele
max_ele = org_arr[-1] * r
for i in range(len(org_arr) - 1, -1, -1):
	if max_ele < org_arr[i] * r:
		max_ele = org_arr[i] * r
	precal_suffmax[i] = max_ele
max_sum = float('-inf')
for i in range(len(org_arr)):
	max_sum = max(max_sum, precal_premax[i] + precal_suffmax[i] + q * org_arr[i])
print(max_sum)


(_, x, y, z) = map(int, input().split())
a = list(map(int, input().split()))

def ans(x, y, z, a):
	(dummy_x, dummy_x_y, dummy_x_y_z) = [-1 * float('inf')] * 3
	for e in a:
		dummy_x = max(dummy_x, e * x)
		dummy_x_y = max(dummy_x_y, dummy_x + e * y)
		dummy_x_y_z = max(dummy_x_y_z, dummy_x_y + e * z)
	return dummy_x_y_z
print(ans(x, y, z, a))


import sys
input = sys.stdin.readline
(n, p, q, r) = map(int, input().split())
l = list(map(int, input().split()))
dpleft = [float('-inf') for _ in range(n)]
dpright = [0 for _ in range(n)]
leftmax = float('-inf')
for i in range(n):
	leftmax = max(leftmax, p * l[i])
	dpleft[i] = leftmax
rightmax = float('-inf')
for i in range(n - 1, -1, -1):
	rightmax = max(rightmax, r * l[i])
	dpright[i] = rightmax
ans = float('-inf')
for i in range(n):
	ans = max(ans, dpleft[i] + q * l[i] + dpright[i])
print(ans)


(n, p, q, r) = map(int, input().split())
nums = list(map(int, input().split()))
dp = [[0 for _ in range(n + 1)] for _ in range(4)]
dp[0][0] = 0
coef = [p, q, r]
for i in range(1, 4):
	for j in range(1, n + 1):
		if j == 1:
			dp[i][j] = dp[i - 1][j] + coef[i - 1] * nums[j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j] + coef[i - 1] * nums[j - 1], dp[i][j - 1])
print(dp[3][n])


(n, p, q, r) = list(map(int, input().split()))
arr = list(map(int, input().split()))
premax = []
suffmax = []
for i in arr:
	premax.append(i * p)
	suffmax.append(i * r)
for i in range(1, n):
	premax[i] = max(premax[i], premax[i - 1])
for i in range(2, n + 1):
	suffmax[-i] = max(suffmax[-i], suffmax[-i + 1])
maxx = float('-inf')
for j in range(0, n):
	if maxx < premax[j] + q * arr[j] + suffmax[j]:
		maxx = premax[j] + q * arr[j] + suffmax[j]
print(maxx)


def modified_pre_max(arr, p):
	n = len(arr)
	arr1 = ['None'] * n
	arr1[0] = arr[0] * p
	for i in range(1, n):
		arr1[i] = max(arr1[i - 1], arr[i] * p)
	return arr1

def modified_suf_max(arr, r):
	n = len(arr)
	arr1 = ['None'] * n
	arr1[n - 1] = arr[n - 1] * r
	for i in range(n - 2, -1, -1):
		arr1[i] = max(arr1[i + 1], arr[i] * r)
	return arr1
(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
ans = float('-inf')
arr_pre_max = modified_pre_max(arr, p)
arr_suf_max = modified_suf_max(arr, r)
for i in range(0, n):
	current_ans = arr_pre_max[i] + arr[i] * q + arr_suf_max[i]
	ans = max(ans, current_ans)
print(ans)


def preMax(arr, coeff):
	tempArr = [arr[0] * coeff]
	for n in range(1, len(arr)):
		tempArr.insert(n, max(arr[n] * coeff, tempArr[n - 1]))
	return tempArr

def suffMax(arr, coeff):
	tempArr = [arr[-1] * coeff]
	for n in range(len(arr) - 1, 0, -1):
		tempArr.insert(0, max(arr[n - 1] * coeff, tempArr[0]))
	return tempArr
coeff = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
pMax = preMax(arr, coeff[1])
sMax = suffMax(arr, coeff[3])
ans = None
for n in range(0, len(arr)):
	tempAns = pMax[n] + arr[n] * coeff[2] + sMax[n]
	if ans == None:
		ans = tempAns
	else:
		ans = max(ans, tempAns)
print(ans)


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) = 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) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
maxi = -1000000000000000000000
b = [a[0]]
c = [a[-1]]
if p > 0:
	for i in range(1, n):
		b.append(max(b[i - 1], a[i]))
else:
	for i in range(1, n):
		b.append(min(b[i - 1], a[i]))
if r > 0:
	for i in range(1, n):
		c.append(max(c[i - 1], a[-i - 1]))
else:
	for i in range(1, n):
		c.append(min(c[i - 1], a[-i - 1]))
for j in range(n):
	s = p * b[j] + q * a[j] + r * c[-j - 1]
	maxi = max(maxi, s)
print(maxi)


def R():
	return map(int, input().split())

def I():
	return int(input())

def S():
	return str(input())

def L():
	return list(R())
from collections import Counter
import math
import sys
from itertools import permutations
(n, p, q, r) = R()
a = L()
dp1 = [-math.inf] * (n + 1)
dp2 = [-math.inf] * (n + 1)
dp3 = [-math.inf] * (n + 1)
for i in range(n):
	dp1[i + 1] = max(dp1[i], a[i] * p)
	dp2[i + 1] = max(dp2[i], a[i] * q + dp1[i + 1])
	dp3[i + 1] = max(dp3[i], a[i] * r + dp2[i + 1])
print(dp3[n])


(n, p, q, r) = [int(i) for i in input().split(' ')]
inp_arr = [int(i) for i in input().split(' ')]
prefix_max = []
suffix_max = []
maxi = -2 ** 63
for i in inp_arr:
	if i * p > maxi:
		maxi = i * p
	prefix_max.append(maxi)
maxi = -2 ** 63
for i in range(n - 1, -1, -1):
	if inp_arr[i] * r > maxi:
		maxi = inp_arr[i] * r
	suffix_max.append(maxi)
suffix_max.reverse()
maxi = -2 ** 63
for i in range(n):
	if prefix_max[i] + suffix_max[i] + inp_arr[i] * q > maxi:
		maxi = prefix_max[i] + suffix_max[i] + inp_arr[i] * q
print(maxi)


import sys
(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
suffix_max = [0] * n
suffix_max[n - 1] = r * arr[n - 1]
for i in range(n - 2, -1, -1):
	suffix_max[i] = max(suffix_max[i + 1], r * arr[i])
max_left = -1 * sys.maxsize * 10 ** 15
ans = -1 * sys.maxsize * 10 ** 15
for j in range(0, n):
	max_left = max(max_left, p * arr[j])
	max_right = suffix_max[j]
	max_value_1 = q * arr[j]
	ans = max(ans, max_left + max_right + max_value_1)
print(ans)


def maxe(a, b):
	if a > b:
		return a
	elif a < b:
		return b
	else:
		return a

def pmmax(a, p):
	x = 0
	a[x] = a[x] * p
	max = a[0]
	y = x + 1
	cap = len(a) - 1
	while y != cap + 1:
		max = maxe(max, p * a[y])
		a[y] = max
		y = y + 1
	return a

def smmax(a, r):
	x = len(a) - 1
	a[x] = a[x] * r
	max = a[x]
	y = x - 1
	while y != -1:
		max = maxe(max, r * a[y])
		a[y] = max
		y = y - 1
	return a

def main():
	(n, p, q, r) = list(map(int, input().strip().split()))[:4]
	a = []
	a = list(map(int, input().strip().split()))[:n]
	b = list(a)
	b = pmmax(b, p)
	c = list(a)
	c = smmax(c, r)
	start = 0
	finish = len(a) - 1
	max = a[0] * p + a[0] * q + a[0] * r
	max = maxe(max, a[finish] * p + a[finish] * q + a[finish] * r)
	st = 1
	i = 0
	while start != finish:
		max = maxe(max, a[start] * p + a[start] * q + a[start] * r)
		max = maxe(max, a[start] * p + a[start] * q + c[start + 1])
		if start != 0:
			max = maxe(max, b[start - 1] + a[start] * q + a[start] * r)
			max = maxe(max, b[start - 1] + a[start] * q + c[start + 1])
		start = start + 1
	print(max)
main()


import sys

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_int():
	return map(int, sys.stdin.readline().strip().split())
(n, p, q, r) = get_int()
arr = get_list()
p_max = [0] * n
r_max = [0] * n
ans = -1e+20
p_max[0] = p * arr[0]
r_max[n - 1] = r * arr[n - 1]
for i in range(1, n):
	p_max[i] = max(p * arr[i], p_max[i - 1])
for i in range(n - 2, -1, -1):
	r_max[i] = max(r_max[i + 1], r * arr[i])
for i in range(0, n):
	ans = max(ans, p_max[i] + q * arr[i] + r_max[i])
print(ans)


(n, p, q, r) = map(int, input().split())
alist = list(map(int, input().split()))
(a, b, c) = (-1e+20, -1e+20, -1e+20)
for i in range(n):
	a = max(a, alist[i] * p)
	b = max(b, a + alist[i] * q)
	c = max(c, b + alist[i] * r)
print(c)


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
from sys import maxsize
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
(n, p, q, r) = map(int, input().split())
dp = [[0] * (n + 1)] * 4
a = list(map(int, input().split()))
ans1 = -1e+22
ans2 = -1e+22
ans3 = -1e+22
for i in a:
	ans1 = max(ans1, p * i)
	ans2 = max(ans2, ans1 + q * i)
	ans3 = max(ans3, ans2 + r * i)
print(ans3)


a = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
(p, q, r) = (a[1], a[2], a[3])
suff = [0 for i in range(a[0])]
suff[len(suff) - 1] = arr[len(arr) - 1] * r
for i in range(len(arr) - 2, -1, -1):
	suff[i] = max(suff[i + 1], arr[i] * r)
pre = arr[0] * p
pre = max(pre, arr[0] * p)
c = pre + arr[0] * q + suff[0]
ma = c
for i in range(1, len(arr)):
	pre = max(pre, arr[i] * p)
	c = pre + arr[i] * q + suff[i]
	ma = max(ma, c)
print(ma)


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


read_int = lambda string: list(map(int, string.split()))

def max_until(k, arr, v):
	x = [None] * len(arr)
	x[0] = k * arr[0] + v[0]
	for i in range(1, len(arr)):
		x[i] = max(x[i - 1], k * arr[i] + v[i])
	return x

def main():
	k = read_int(input())
	arr = read_int(input())
	x = max_until(k[1], arr, [0] * len(arr))
	y = max_until(k[2], arr, x)
	z = max_until(k[3], arr, y)
	print(z[-1])
main()


(n, q, s, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
pmax_f = [a[0]]
pmin_f = [a[0]]
for i in range(n):
	pmax_f += [max(pmax_f[-1], a[i])]
	pmin_f += [min(pmin_f[-1], a[i])]
pmax_e = [a[-1]]
pmin_e = [a[-1]]
for i in range(n):
	i = n - i - 1
	pmax_e += [max(pmax_e[-1], a[i])]
	pmin_e += [min(pmin_e[-1], a[i])]
ma = 'False'
for i in range(n):
	nat = s * a[i]
	nat += max(pmax_f[i + 1] * q, pmin_f[i + 1] * q)
	i = n - i - 1
	nat += max(pmax_e[i + 1] * r, pmin_e[i + 1] * r)
	if ma == 'False':
		ma = nat
	ma = max(ma, nat)
print(ma)


(n, p, q, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
(num1, num2, num3) = (-1e+20, -1e+20, -1e+20)
for x in a:
	num1 = max(num1, p * x)
	num2 = max(num2, num1 + q * x)
	num3 = max(num3, num2 + r * x)
print(num3)


(n, a, b, c) = map(int, input().split())
array = list(map(int, input().split()))
val_max = (10 ** 20 + 1) * -1
array_b = []
for x in range(n):
	if a * array[x] > val_max:
		val_max = a * array[x]
	array_b.append(b * array[x] + val_max)
resp = (10 ** 20 + 1) * -1
val_max = (10 ** 18 + 1) * -1
for y in range(n):
	if c * array[n - y - 1] > val_max:
		val_max = c * array[n - y - 1]
	if array_b[n - y - 1] + val_max > resp:
		resp = array_b[n - y - 1] + val_max
print(resp)


vals = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
dp = [[0 for i in range(vals[0])] for i in range(3)]
n = vals[0]
ind = 0
for i in vals[1:]:
	dp[ind][n - 1] = i * arr[-1]
	for j in range(n - 2, -1, -1):
		dp[ind][j] = max(dp[ind][j + 1], i * arr[j])
	ind += 1
ans = -float('inf')
dp2 = [0 for i in range(n)]
dp2[-1] = arr[-1] * vals[2] + dp[2][-1]
for i in range(n - 2, -1, -1):
	dp2[i] = max(dp2[i + 1], arr[i] * vals[2] + dp[2][i])
for i in range(n):
	ans = max(ans, dp2[i] + arr[i] * vals[1])
print(ans)


(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)


(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, r) = input().split()
x = []
x = list(map(int, input().split()))
p = int(p)
q = int(q)
r = int(r)
for i in range(int(n)):
	t = int(x[i])
	if i == 0:
		a = t * p
		b = a + t * q
		c = b + t * r
	else:
		if a < t * p:
			a = t * p
		if b < a + t * q:
			b = a + t * q
		if c < b + t * r:
			c = b + t * r
print(c)


(n, p, q, r) = map(int, input().split())
z = list(map(int, input().split()))
pmini = [z[0]]
pmaxa = [z[0]]
xa = [z[0]]
for i in range(1, len(z)):
	pmini.append(min(pmini[-1], z[i]))
	pmaxa.append(max(pmaxa[-1], z[i]))
rmini = [0 for i in range(len(z))]
rmaxa = [0 for i in range(len(z))]
rmini[-1] = z[-1]
rmaxa[-1] = z[-1]
for i in range(len(z) - 2, -1, -1):
	rmini[i] = min(z[i], rmini[i + 1])
	rmaxa[i] = max(z[i], rmaxa[i + 1])
maxa = z[0] * (p + q + r)
for i in range(len(z)):
	if p < 0:
		if r < 0:
			maxa = max(maxa, z[i] * q + pmini[i] * p + rmini[i] * r)
		else:
			maxa = max(maxa, z[i] * q + pmini[i] * p + rmaxa[i] * r)
	elif r < 0:
		maxa = max(maxa, z[i] * q + pmaxa[i] * p + rmini[i] * r)
	else:
		maxa = max(maxa, z[i] * q + pmaxa[i] * p + rmaxa[i] * r)
print(maxa)


def binarySearch(arr, x):
	l = 0
	r = len(arr) - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1
(n, p, q, r) = map(int, input().split())
ar = list(map(int, input().split()))
dp = []
inf = -9999999999999999999999999999999999999
for i in range(n + 1):
	dp.append([inf, inf, inf])
for i in range(1, n + 1):
	dp[i][0] = max(dp[i - 1][0], ar[i - 1] * p)
	dp[i][1] = max(dp[i - 1][1], dp[i][0] + ar[i - 1] * q)
	dp[i][2] = max(dp[i - 1][2], dp[i][1] + ar[i - 1] * r)
print(dp[-1][-1])


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)
		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)


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


a = list(map(int, input().split()))
arr = list(map(int, input().split()))
n = a[0]
dp = [[0 for i in range(4)] for j in range(n + 1)]
for i in range(4):
	dp[0][i] = (-10) ** 27
for i in range(1, n + 1):
	for j in range(1, 4):
		x = arr[i - 1] * a[j] + dp[i][j - 1]
		y = dp[i - 1][j]
		dp[i][j] = max(x, y)
print(dp[n][3])


R = lambda : map(int, input().split())
(n, p, q, r) = R()
arr = list(R())
(lmi, lmx, rmi, rmx) = (arr[:], arr[:], arr[:], arr[:])
for i in range(1, n):
	lmi[i] = min(lmi[i], lmi[i - 1])
	lmx[i] = max(lmx[i], lmx[i - 1])
for i in range(n - 2, -1, -1):
	rmi[i] = min(rmi[i], rmi[i + 1])
	rmx[i] = max(rmx[i], rmx[i + 1])
print(max((max(lmi[i] * p, lmx[i] * p) + arr[i] * q + max(rmi[i] * r, rmx[i] * r) for i in range(n))))


(n, p, q, r) = map(int, input().split())
x = list(map(int, input().split()))
p_max = []
q_max = []
r_max = []
p_max.append(p * x[0])
for i in range(1, n):
	p_max.append(max(p_max[i - 1], p * x[i]))
q_max.append(x[0] * q + p_max[0])
for i in range(1, n):
	q_max.append(max(q_max[i - 1], p_max[i] + x[i] * q))
ans = -10 ** 30
for i in range(0, n):
	ans = max(ans, r * x[i] + q_max[i])
print(ans)


def f(n, p, q, r, a):
	dp = [[0 for i in range(n)] for j in range(3)]
	dp[0][0] = p * a[0]
	dp[1][0] = dp[0][0] + q * a[0]
	dp[2][0] = dp[1][0] + r * a[0]
	for i in range(1, n):
		dp[0][i] = max(dp[0][i - 1], p * a[i])
		dp[1][i] = max(dp[1][i - 1], dp[0][i] + q * a[i])
		dp[2][i] = max(dp[2][i - 1], dp[1][i] + r * a[i])
	return dp[2][n - 1]
x = input()
x1 = x.split(' ')
x2 = [int(t) for t in x1]
y = input()
y1 = y.split(' ')
y2 = [int(t) for t in y1]
print(f(x2[0], x2[1], x2[2], x2[3], y2))


import sys
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))


s = input()
inf = 1e+30
s = [int(x) for x in s.split()]
n = s[0]
p = s[1]
q = s[2]
r = s[3]
a = input()
a = [int(x) for x in a.split()]
dp = []
for i in range(n + 1):
	dp.append(0)
dp[0] = -inf
i = 1
while i <= n:
	now = p * a[i - 1]
	dp[i] = max(dp[i - 1], now)
	i = i + 1
i = 1
while i <= n:
	now = q * a[i - 1]
	dp[i] = max(dp[i - 1], dp[i] + now)
	i = i + 1
i = 1
ans = -inf
while i <= n:
	now = r * a[i - 1]
	dp[i] = max(dp[i - 1], dp[i] + now)
	ans = max(ans, dp[i])
	i = i + 1
print(ans)


(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
length = len(arr)
pmax = [0] * length
smax = [0] * length
pmax[0] = p * arr[0]
smax[length - 1] = r * arr[length - 1]
answer = -100000000000000000000000000000
for i in range(1, length):
	pmax[i] = max(pmax[i - 1], p * arr[i])
for i in range(length - 2, -1, -1):
	smax[i] = max(smax[i + 1], r * arr[i])
for i in range(0, length):
	x = pmax[i] + q * arr[i] + smax[i]
	answer = max(answer, x)
print(answer)


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

def ring(arr, p, q, r):
	max_ = p * arr[0] + q * arr[0] + r * arr[0]
	maxr = [r * arr[-1]]
	maxl = [p * arr[0]]
	for i in range(1, len(arr)):
		maxl.append(max(p * arr[i], maxl[i - 1]))
	for i in range(len(arr) - 2, -1, -1):
		maxr.append(max(maxr[-1], r * arr[i]))
	maxr.reverse()
	for j in range(len(arr)):
		qa = q * arr[j]
		pa = maxl[j]
		ra = maxr[j]
		if pa + qa + ra > max_:
			max_ = pa + qa + ra
	print(max_)
ring(arr, p, q, r)


(n, p, q, r) = map(int, input().split())
l = list(map(int, input().split()))
dp = [[0 for i in range(n)] for j in range(3)]
for i in range(3):
	for j in range(n):
		if i == 0:
			if j == 0:
				dp[i][j] = l[j] * p
			else:
				dp[i][j] = max(dp[i][j - 1], l[j] * p)
		elif i == 1:
			if j == 0:
				dp[i][j] = dp[i - 1][j] + l[j] * q
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j] + l[j] * q)
		elif j == 0:
			dp[i][j] = dp[i - 1][j] + l[j] * r
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j] + l[j] * r)
print(dp[-1][-1])


(n, p, q, r) = input().split(' ')
arr = input().split(' ')
n = int(n)
p = int(p)
q = int(q)
r = int(r)
arr = [int(x) for x in arr]
prefix_max = []
maximum = float('-inf')
for i in range(len(arr)):
	prefix_max.append(max(maximum, p * arr[i]))
	maximum = prefix_max[-1]
maxi = float('-inf')
suffix_max = [1 ** x for x in range(len(arr))]
for i in range(len(arr) - 1, -1, -1):
	suffix_max[i] = max(r * arr[i], maxi)
	maxi = suffix_max[i]
max_len = [1 for x in range(len(arr))]
for j in range(len(arr)):
	max_len[j] = prefix_max[j] + q * arr[j] + suffix_max[j]
print(max(max_len))


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))


(n, p, q, r) = map(int, input().split())
nums = list(map(int, input().split()))
dp0 = [0 for i in range(100000)]
dp1 = [0 for i in range(100000)]
dp2 = [0 for i in range(100000)]
dp0[0] = nums[0] * p
for i in range(1, n):
	dp0[i] = max(dp0[i - 1], nums[i] * p)
dp1[0] = dp0[0] + nums[0] * q
for i in range(1, n):
	dp1[i] = max(dp1[i - 1], dp0[i] + nums[i] * q)
dp2[0] = dp1[0] + nums[0] * r
for i in range(1, n):
	dp2[i] = max(dp2[i - 1], dp1[i] + nums[i] * r)
print(dp2[n - 1])


(n, p, q, r) = map(int, input().split())
ai = list(map(int, input().split()))
maxp = ai[-1] * p
maxq = ai[-1] * q
maxr = ai[-1] * r
maxqr = maxq + maxr
ans = maxqr + maxp
for i in range(n - 2, -1, -1):
	maxr = max(maxr, ai[i] * r)
	maxqr = max(maxqr, ai[i] * q + maxr)
	ans = max(ans, maxqr + ai[i] * p)
print(ans)


(t, p, q, r) = map(int, input().split())
l = [int(i) for i in input().split()]
prex = [0 for i in range(len(l))]
suff = [0 for i in range(len(l))]
prex[0] = l[0] * p
n = len(l)
for i in range(1, n):
	prex[i] = max(l[i] * p, prex[i - 1])
suff[n - 1] = l[n - 1] * r
for i in range(n - 2, -1, -1):
	suff[i] = max(l[i] * r, suff[i + 1])
maxx = -3 * 10 ** 20
for i in range(n):
	maxx = max(maxx, prex[i] + q * l[i] + suff[i])
print(maxx)


(n, x, y, z) = map(int, input().split(' '))
y1 = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
	if i == 0:
		dp[i] = x * y1[i]
	else:
		dp[i] = max(x * y1[i] + dp[i], dp[i - 1])
for i in range(n):
	if i == 0:
		dp[i] = y * y1[i] + dp[i]
	else:
		dp[i] = max(dp[i - 1], dp[i] + y1[i] * y)
for i in range(n):
	if i == 0:
		dp[i] = z * y1[i] + dp[i]
	else:
		dp[i] = max(dp[i - 1], dp[i] + y1[i] * z)
print(dp[-1])


from typing import List
import sys

class Solution:

	def maxExpr(self, nums: List[int], p: int, q: int, r: int) -> int:
		n = len(nums)
		if n < 1:
			return 0
		pmax = [0] * n
		smax = [0] * n
		pmax[0] = p * nums[0]
		for i in range(1, n):
			pmax[i] = max(pmax[i - 1], p * nums[i])
		smax[n - 1] = r * nums[n - 1]
		for i in range(n - 2, -1, -1):
			smax[i] = max(smax[i + 1], r * nums[i])
		max_expr = -2 ** 63
		for i in range(0, n):
			curr_expr = pmax[i] + q * nums[i] + smax[i]
			max_expr = max(max_expr, curr_expr)
		return max_expr
sol = Solution()
(n, p, q, r) = map(int, input().split(' '))
x = input()
l = list(map(int, x.split()))
max_expr = sol.maxExpr(l, p, q, r)
print(max_expr)


import sys
(n, p, q, r) = [int(x) for x in input().split()]
pmax = [] * n
smax = [] * n
arr = list(map(int, input().split()))[:n]
pmax.append(p * arr[0])
for i in range(1, n):
	pmax.append(max(pmax[i - 1], p * arr[i]))
smax.append(r * arr[n - 1])
for i in range(n - 2, -1, -1):
	smax.insert(0, max(smax[0], r * arr[i]))
if p == 0 and q == 0 and (r == 0):
	print(0)
else:
	ans = pmax[0] + q * arr[0] + smax[0]
	i = 1
	while i < n:
		ans = max(ans, pmax[i] + q * arr[i] + smax[i])
		i += 1
	print(ans)


(n, p, q, r) = map(int, input().split())
x = [int(i) for i in input().split()]
x1 = [0] * n
x2 = [0] * n
x3 = [0] * n
x1[0] = p * x[0]
x2[0] = x1[0] + q * x[0]
x3[0] = x2[0] + r * x[0]
for i in range(1, len(x)):
	x1[i] = max(x1[i - 1], p * x[i])
	x2[i] = max(x2[i - 1], q * x[i] + x1[i])
	x3[i] = max(x3[i - 1], r * x[i] + x2[i])
print(x3[n - 1])


(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
INF = float('inf')
R = [-INF] * n
R[-1] = a[-1] * r
for i in range(n - 2, -1, -1):
	R[i] = max(R[i + 1], a[i] * r)
P = [-INF] * n
P[0] = a[0] * p
for i in range(1, n):
	P[i] = max(P[i - 1], a[i] * p)
num = -INF
for i in range(n):
	num = max(num, P[i] + a[i] * q + R[i])
print(num)


import sys
input = sys.stdin.readline
(n, p, q, r) = map(int, input().split())
a = list(map(int, input().split()))
ml = [a[0]]
Ml = [a[0]]
for i in range(1, n):
	ml.append(min(ml[-1], a[i]))
	Ml.append(max(Ml[-1], a[i]))
mr = [a[-1]]
Mr = [a[-1]]
for i in range(n - 2, -1, -1):
	mr.append(min(mr[-1], a[i]))
	Mr.append(max(Mr[-1], a[i]))
mr = mr[::-1]
Mr = Mr[::-1]
ans = -float('inf')
for i in range(n):
	ans = max(ans, p * ml[i] + q * a[i] + r * mr[i])
	ans = max(ans, p * ml[i] + q * a[i] + r * Mr[i])
	ans = max(ans, p * Ml[i] + q * a[i] + r * mr[i])
	ans = max(ans, p * Ml[i] + q * a[i] + r * Mr[i])
print(ans)


a = [int(x) for x in input().split()]
b = [int(y) for y in input().split()]
n = a[0]
(p, q, r) = (a[1], a[2], a[3])
left = []
right = []
for i in range(n):
	left.append(b[i] * p)
	right.append(b[i] * r)
prefixMax = [0] * n
temp = -10000000000000000000
i = 0
while i < n:
	temp = max(temp, left[i])
	prefixMax[i] = temp
	i += 1
temp = -10000000000000000000
suffixMax = [0] * n
i = n - 1
while i >= 0:
	temp = max(temp, right[i])
	suffixMax[i] = temp
	i -= 1
ans = -10000000000000000000
for j in range(n):
	aJ = q * b[j]
	lMax = prefixMax[j]
	rMax = suffixMax[j]
	s = aJ + lMax + rMax
	ans = max(ans, s)
print(ans)


import sys

def getX(ai, aj, ak):
	return ai * p + aj * q + ak * r
inpt = input().split()
n = int(inpt[0])
p = int(inpt[1])
q = int(inpt[2])
r = int(inpt[3])
arr = list(map(int, input().split()))
minLeft = []
maxLeft = []
minRight = []
maxRight = []
for i in range(n):
	if i == 0:
		minLeft.append(arr[i])
		maxLeft.append(arr[i])
	else:
		minLeft.append(min(minLeft[len(minLeft) - 1], arr[i]))
		maxLeft.append(max(maxLeft[len(maxLeft) - 1], arr[i]))
arr.reverse()
for i in range(n):
	if i == 0:
		minRight.append(arr[i])
		maxRight.append(arr[i])
	else:
		minRight.append(min(minRight[len(minRight) - 1], arr[i]))
		maxRight.append(max(maxRight[len(maxRight) - 1], arr[i]))
minRight.reverse()
maxRight.reverse()
result = -9223372036854775808
arr.reverse()
for j in range(n):
	if p < 0:
		ai = minLeft[j]
	else:
		ai = maxLeft[j]
	if r < 0:
		ak = minRight[j]
	else:
		ak = maxRight[j]
	result = max(result, getX(ai, arr[j], ak))
print(result)


import sys
(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)


def readints():
	return [int(item) for item in input().split()]

class Solver:

	def main(self):
		(n, p, q, r) = readints()
		a = [0] + readints()
		dp = [[0 for _ in range(3)] for _ in range(n + 1)]
		dp[1][0] = p * a[1]
		dp[1][1] = (p + q) * a[1]
		dp[1][2] = (p + q + r) * a[1]
		for i in range(2, n + 1):
			dp[i][0] = max(dp[i - 1][0], p * a[i])
			dp[i][1] = max(p * a[i] + q * a[i], dp[i - 1][0] + q * a[i], dp[i - 1][1])
			dp[i][2] = max(p * a[i] + q * a[i] + r * a[i], dp[i - 1][0] + q * a[i] + r * a[i], dp[i - 1][1] + r * a[i], dp[i - 1][2])
		print(dp[n][2])
Solver().main()


(n, p, q, r) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = [p * arr[0]]
for i in range(1, n):
	arr1.append(max(p * arr[i], arr1[-1]))
arr2 = [arr1[0] + q * arr[0]]
for i in range(1, n):
	arr2.append(max(arr2[-1], arr1[i] + q * arr[i]))
arr3 = [arr2[0] + r * arr[0]]
for i in range(1, n):
	arr3.append(max(arr3[-1], arr2[i] + r * arr[i]))
print(arr3[-1])


import sys
initial_inp = []
inp = []
n = input().split()
count = int(n[0], 10)
p = int(n[1], 10)
q = int(n[2], 10)
r = int(n[3], 10)
arrString = input().split()
arr = count * [None]
for i in range(0, count):
	arr[i] = int(arrString[i], 10)

def maximum(a, b):
	if a < b:
		return b
	else:
		return a
pmax = [1] * count
pmax[0] = arr[0] * p
for i in range(1, count):
	pmax[i] = maximum(pmax[i - 1], p * arr[i])
smax = [1] * count
smax[count - 1] = arr[count - 1] * r
for i in range(count - 2, -1, -1):
	smax[i] = maximum(smax[i + 1], r * arr[i])
ans = -sys.maxsize - sys.maxsize * sys.maxsize * 10
for i in range(0, count):
	ans = maximum(pmax[i] + q * arr[i] + smax[i], ans)
print(ans)


(n, p, q, r) = map(int, input().split())
mp = mq = mr = -1e+20
for i in map(int, input().split()):
	mp = max(mp, p * i)
	mq = max(mq, mp + q * i)
	mr = max(mr, mq + r * i)
print(mr)


f = lambda : map(int, input().split())
(n, p, q, r) = f()
a = list(f())
x = [t * p for t in a]
y = [t * q for t in a]
z = [t * r for t in a]
for i in range(n - 1, 0, -1):
	z[i - 1] = max(z[i - 1], z[i])
for i in range(1, n):
	x[i] = max(x[i - 1], x[i])
print(max((x[i] + y[i] + z[i] for i in range(n))))


f = lambda : map(int, input().split())
(n, p, q, r) = f()
a = b = c = -10 ** 19
d = list(f())
for i in range(n):
	a = max(a, d[i] * p)
	b = max(b, a + d[i] * q)
	c = max(c, b + d[i] * r)
print(c)


(n, p, q, r) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
maxP = []
maxim = float('-inf')
for i in range(n):
	maxP.append(arr[i] * p)
	maxim = max(maxim, arr[i] * p)
	maxP[i] = maxim
maxim = float('-inf')
maxR = [float('-inf') for x in range(n)]
for i in range(n - 1, -1, -1):
	maxR[i] = arr[i] * r
	maxim = max(maxim, arr[i] * r)
	maxR[i] = maxim
ans = float('-inf')
for i in range(n):
	ans = max(ans, maxP[i] + arr[i] * q + maxR[i])
print(ans)


R = lambda : map(int, input().split())
(n, p, q, r) = R()
arr = list(R())
ps = [p * x for x in arr]
for i in range(1, n):
	ps[i] = max(ps[i], ps[i - 1])
pqs = [ps[i] + arr[i] * q for i in range(n)]
for i in range(1, n):
	pqs[i] = max(pqs[i], pqs[i - 1])
print(max((pqs[i] + r * arr[i] for i in range(n))))


def fdp():
	(n, P, Q, R) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	dpP = [0 for j in range(n)]
	dpQ = [0 for j in range(n)]
	dpR = [0 for j in range(n)]
	dpP[0] = P * l[0]
	dpQ[0] = Q * l[0] + dpP[0]
	dpR[0] = R * l[0] + dpQ[0]
	for i in range(1, n):
		dpP[i] = max(dpP[i - 1], P * l[i])
		dpQ[i] = max(dpP[i] + Q * l[i], dpQ[i - 1])
		dpR[i] = max(dpQ[i] + R * l[i], dpR[i - 1])
	print(dpR[n - 1])
fdp()


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

def select_and_multiply(x, arr):
	if x >= 0:
		return x * arr[-1]
	return x * arr[0]

def solve():
	minFromLeft = [None for i in range(n)]
	maxFromLeft = [None for i in range(n)]
	minFromRight = [None for i in range(n)]
	maxFromRight = [None for i in range(n)]
	minFromLeft[0] = arr[0]
	maxFromLeft[0] = arr[0]
	minFromRight[-1] = arr[-1]
	maxFromRight[-1] = arr[-1]
	for i in range(1, n):
		minFromLeft[i] = min(minFromLeft[i - 1], arr[i])
		maxFromLeft[i] = max(maxFromLeft[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		minFromRight[i] = min(minFromRight[i + 1], arr[i])
		maxFromRight[i] = max(maxFromRight[i + 1], arr[i])
	result = float('-inf')
	for i in range(n):
		a = maxFromLeft[i] if p >= 0 else minFromLeft[i]
		b = arr[i]
		c = maxFromRight[i] if r >= 0 else minFromRight[i]
		result = max(result, a * p + b * q + c * r)
	return result
print(solve())


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


from copy import deepcopy as dc
(n, p, q, r) = map(int, input().strip().split(' '))
li = list(map(int, input().strip().split(' ')))
p_prefix = [0 for i in range(n)]
r_suffix = [0 for i in range(n)]
p_prefix[0] = p * li[0]
ma = max
for i in range(1, n):
	p_prefix[i] = ma(p * li[i], p_prefix[i - 1])
r_suffix[n - 1] = r * li[n - 1]
for i in range(n - 2, -1, -1):
	r_suffix[i] = ma(r * li[i], r_suffix[i + 1])
maxi = float('-inf')
for i in range(n):
	maxi = ma(p_prefix[i] + q * li[i] + r_suffix[i], maxi)
print(maxi)


import math
(n, p, q, r) = map(int, input().split())
aa = [int(i) for i in input().split()]
(pp, qq, rr) = (-math.inf, -math.inf, -math.inf)
for i in aa:
	pp = max(pp, p * i)
	qq = max(qq, pp + q * i)
	rr = max(rr, qq + r * i)
print(rr)


def maxValue(arr, n, p, q, r):
	preMap = [0] * n
	preMap[0] = p * arr[0]
	suffMap = [0] * n
	suffMap[n - 1] = r * arr[n - 1]
	for i in range(1, n):
		if preMap[i - 1] >= p * arr[i]:
			preMap[i] = preMap[i - 1]
		else:
			preMap[i] = p * arr[i]
	for i in range(n - 2, -1, -1):
		if suffMap[i + 1] >= r * arr[i]:
			suffMap[i] = suffMap[i + 1]
		else:
			suffMap[i] = r * arr[i]
	maxm = float('-inf')
	for i in range(n):
		if suffMap[i] + preMap[i] + q * arr[i] >= maxm:
			maxm = suffMap[i] + preMap[i] + q * arr[i]
	return maxm
li = list(map(int, input().split()))
arr = list(map(int, input().split()))
print(maxValue(arr, li[0], li[1], li[2], li[3]))


import sys
(n, p, q, r) = map(int, input().split())
lis = [int(temp) for temp in input().split()]
a = lis[0] * p
b = a + lis[0] * q
c = b + lis[0] * r
for x in lis:
	a = max(a, x * p)
	b = max(b, a + x * q)
	c = max(c, b + x * r)
print(c)


(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)


P_I = 0
Q_I = 1
R_I = 2

def solve(n, pqr, a):
	max_p = [0 for _ in range(n)]
	max_r = [0 for _ in range(n)]
	max_p[0] = pqr[P_I] * a[0]
	max_r[n - 1] = pqr[R_I] * a[n - 1]
	for i in range(1, n):
		max_p[i] = max(max_p[i - 1], pqr[P_I] * a[i])
	for k in range(n - 2, -1, -1):
		max_r[k] = max(max_r[k + 1], pqr[R_I] * a[k])
	m = -3000000000000000000000
	for j in range(n):
		prod = pqr[Q_I] * a[j]
		s = max_p[j] + prod + max_r[j]
		m = max(s, m)
	return m
line1 = input().split()
n = int(line1[0])
pqr = [int(i) for i in line1[1:]]
a = [int(i) for i in input().split()]
print(solve(n, pqr, a))