Vasya has n items lying in a line. The items are consecutively numbered by numbers from 1 to n in such a way that the leftmost item has number 1, the rightmost item has number n. Each item has a weight, the i-th item weights w_{i} kilograms.

Vasya needs to collect all these items, however he won't do it by himself. He uses his brand new robot. The robot has two different arms — the left one and the right one. The robot can consecutively perform the following actions:   Take the leftmost item with the left hand and spend w_{i} · l energy units (w_{i} is a weight of the leftmost item, l is some parameter). If the previous action was the same (left-hand), then the robot spends extra Q_{l} energy units;  Take the rightmost item with the right hand and spend w_{j} · r energy units (w_{j} is a weight of the rightmost item, r is some parameter). If the previous action was the same (right-hand), then the robot spends extra Q_{r} energy units; 

Naturally, Vasya wants to program the robot in a way that the robot spends as little energy as possible. He asked you to solve this problem. Your task is to find the minimum number of energy units robot spends to collect all items.


-----Input-----

The first line contains five integers n, l, r, Q_{l}, Q_{r} (1 ≤ n ≤ 10^5; 1 ≤ l, r ≤ 100; 1 ≤ Q_{l}, Q_{r} ≤ 10^4).

The second line contains n integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 100).


-----Output-----

In the single line print a single number — the answer to the problem.


-----Examples-----
Input
3 4 4 19 1
42 3 99

Output
576

Input
4 7 2 3 9
1 2 3 4

Output
34



-----Note-----

Consider the first sample. As l = r, we can take an item in turns: first from the left side, then from the right one and last item from the left. In total the robot spends 4·42 + 4·99 + 4·3 = 576 energy units.

The second sample. The optimal solution is to take one item from the right, then one item from the left and two items from the right. In total the robot spends (2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 energy units.

Difficulty: MEDIUM
Tags: Complete search

Mathematics

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
(n, l, r, Ql, Qr) = map(int, input().split())
(s, v) = ([0] * (n + 1), 2 * 10 ** 9)
for (i, wi) in enumerate(map(int, input().split())):
	s[i + 1] = s[i] + wi
for lc in range(0, n + 1):
	rc = n - lc
	c = s[lc] * l + (s[n] - s[lc]) * r
	if lc > rc + 1:
		c += (lc - rc - 1) * Ql
	elif rc > lc + 1:
		c += (rc - lc - 1) * Qr
	v = min(v, c)
print(v)


(n, l, r, ql, qr) = map(int, input().split())
weights = [int(x) for x in input().split()]
curr_sum = 0
cum_sum = list()
for i in weights:
	curr_sum += i
	cum_sum.append(curr_sum)
min_cost = r * curr_sum + (n - 1) * qr
for i in range(1, n + 1):
	taskl = i
	taskr = n - i
	cost = l * cum_sum[taskl - 1] + r * (cum_sum[-1] - cum_sum[taskl - 1])
	if taskl > taskr:
		cost += ql * (taskl - taskr - 1)
	elif taskr > taskl:
		cost += qr * (taskr - taskl - 1)
	min_cost = min(min_cost, cost)
print(min_cost)


def main():
	(n, l, r, Ql, Qr) = list(map(int, input().split()))
	ww = list(map(int, input().split()))
	work = sum(ww) * r + (n - 1) * Qr
	(res, penalty) = ([work], Qr * 2)
	l -= r
	for w in ww[:(n - 1) // 2]:
		work += l * w - penalty
		res.append(work)
	penalty = Ql * 2
	work += l * ww[(n - 1) // 2]
	if n & 1:
		res.append(work)
	else:
		work -= Qr
		res.append(work)
		work -= Ql
	for w in ww[(n + 1) // 2:]:
		work += l * w + penalty
		res.append(work)
	print(min(res))

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
from math import ceil, floor, factorial

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

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

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
(n, l, r, ql, qr) = int_array()
a = [0] + int_array()
for i in range(1, n + 1):
	a[i] += a[i - 1]
s = a[n]
ans = INF
for i in range(n + 1):
	x = a[i] * l + (s - a[i]) * r
	if i > n - i:
		x += (2 * i - n - 1) * ql
	if n - i > i:
		x += (n - 2 * i - 1) * qr
	ans = min(x, ans)
print(ans)


(n, l, r, ql, qr) = list(map(int, input().split()))
w = list(map(int, input().split()))
prefix = [0]
suffix = [sum(w)]
for i in range(n):
	prefix.append(prefix[i] + w[i])
	suffix.append(suffix[i] - w[i])
m = 10000000000.0
for i in range(n + 1):
	res = l * prefix[i] + r * suffix[i]
	if i > n - i:
		res += (2 * i - n - 1) * ql
	if i < n - i:
		res += (n - 2 * i - 1) * qr
	m = min(m, res)
print(m)


(n, l, r, q1, q2) = list(map(int, input().split()))
item = list(map(int, input().split()))
pre = [item[0]] + [0 for i in range(1, n)]
suf = [0 for i in range(0, n - 1)] + [item[n - 1], 0]
for i in range(1, n):
	pre[i] = pre[i - 1] + item[i]
for i in range(n - 2, -1, -1):
	suf[i] = suf[i + 1] + item[i]
ans = 1e+20
for i in range(0, n):
	(a, b) = (i + 1, n - i - 1)
	c = pre[i] * l + suf[i + 1] * r + (q1 * (a - b - 1) if a > b else q2 * (b - a - 1) if b > a else 0)
	ans = min(ans, c)
ans = min(ans, suf[0] * r + q2 * (n - 1))
print(ans)


(n, l, r, ql, qr) = map(int, input().split())
w = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	w[i] += w[i - 1]
s = w[n]
print(min((l * w[i] + r * (s - w[i]) + ql * max(0, 2 * i - n - 1) + qr * max(0, n - 2 * i - 1) for i in range(n + 1))))


(n, l, r, ql, qr) = map(int, input().split())
w = list(map(int, input().split()))
answ = 0
first = 0
last = sum(w)
answ = last * r + (len(w) - 1) * qr
for i in range(n):
	first += w[i]
	last -= w[i]
	tmp = first * l + last * r
	if i + 1 > n - i - 1:
		tmp += ql * (i + 1 - n + i + 1 - 1)
	elif i + 1 < n - i - 1:
		tmp += qr * (n - 2 * i - 3)
	answ = min(answ, tmp)
print(answ)


(n, l, r, ql, qr) = list(map(int, input().split()))
li = list(map(int, input().split()))
ri = li.copy()
ri.append(0)
list(map(lambda x: 0, ri))
ri[0] = 0
ri[1] = li[0]
for i in range(2, len(li) + 1):
	ri[i] = ri[i - 1] + li[i - 1]
minans = 1000000000000000
s1 = 0
for j in range(0, len(li) + 1):
	if j < len(li) / 2:
		s1 = ri[j] * l + ri[len(li)] * r - ri[j] * r + qr * (len(li) - 2 * j - 1)
	elif j > len(li) / 2:
		s1 = ri[j] * l + ri[len(li)] * r - ri[j] * r + ql * (2 * j - len(li) - 1)
	else:
		s1 = ri[j] * l + ri[len(li)] * r - ri[j] * r
	minans = min([s1, minans])
print(minans)


(num, l, r, ql, qr) = list(map(int, input().split()))
ara = [int(i) for i in input().split()]
for i in range(1, num, 1):
	ara[i] = ara[i] + ara[i - 1]
ans = 10 ** 11
for i in range(0, num + 1, 1):
	tr = num - i
	cl = ara[i - 1] if i > 0 else 0
	cr = ara[num - 1] - cl
	pl = max(0, i - tr - 1)
	pr = max(0, tr - i - 1)
	tans = pl * ql + pr * qr + cl * l + cr * r
	ans = min(ans, tans)
print(ans)


path = list(map(int, input().split()))
(n, L, R, QL, QR) = (path[0], path[1], path[2], path[3], path[4])
w = list(map(int, input().split()))
sumpref = [0]
for i in range(1, n + 1):
	sumpref.append(w[i - 1] + sumpref[i - 1])
answer = QR * (n - 1) + sumpref[n] * R
for i in range(1, n + 1):
	energy = L * sumpref[i] + R * (sumpref[n] - sumpref[i])
	if i > n - i:
		energy += (i - (n - i) - 1) * QL
	elif n - i > i:
		energy += (n - i - i - 1) * QR
	if answer > energy:
		answer = energy
print(answer)


(n, l, r, ql, qr) = map(int, input().split())
w = list(map(int, input().split()))
s = [0, *w]
for i in range(1, n + 1):
	s[i] += s[i - 1]
c_min = s[n] * r + (n - 1) * qr
for i in range(1, n + 1):
	cc = l * s[i] + (s[n] - s[i]) * r
	if 2 * i < n:
		cc += (n - 2 * i - 1) * qr
	elif 2 * i > n:
		cc += (i - (n - i) - 1) * ql
	c_min = min(c_min, cc)
print(c_min)


import sys
(n, l, r, ql, qr) = map(int, sys.stdin.readline().strip().split())
w = [int(x) for x in sys.stdin.readline().strip().split()]
s = [0]
for i in range(0, n):
	s.append(s[-1] + w[i])

def cost(left):
	right = n - left
	diff = left - right
	bonus = 0
	if diff > 0:
		bonus = ql * (diff - 1)
	elif diff < 0:
		bonus = qr * (-diff - 1)
	return bonus + l * s[left] + r * (s[n] - s[left])
best = cost(0)
for left in range(1, n + 1):
	c = cost(left)
	if c < best:
		best = c
print(best)


def solve(lst, l, r, left, right):
	left_sum = [0]
	right_sum = [0] * (len(lst) + 1)
	cum_sum = 0
	for i in range(len(lst)):
		cum_sum += lst[i]
		left_sum.append(cum_sum)
	cum_sum = 0
	for i in reversed(range(len(lst))):
		cum_sum += lst[i]
		right_sum[i] = cum_sum
	min_cost = float('inf')
	for i in range(len(lst) + 1):
		cost = left_sum[i] * l + right_sum[i] * r
		if i > n - i:
			cost += left * (2 * i - n - 1)
		elif i < n - i:
			cost += right * (n - 1 - 2 * i)
		min_cost = min(min_cost, cost)
	return min_cost
(n, l, r, left, right) = list(map(int, input().split()))
lst = list(map(int, input().split()))
print(solve(lst, l, r, left, right))


import sys
(n, L, r, QL, QR) = map(int, sys.stdin.readline().split())
W = list(map(int, sys.stdin.readline().split()))
minn = 10 ** 10
SumsL = [0] * n
SumsR = [0] * n
s = 0
for i in range(n):
	s += W[i]
	SumsL[i] = s
for i in range(n - 1):
	ans = L * SumsL[i] + r * (s - SumsL[i])
	if n - (i + 1) > i + 1:
		ans += (abs(n - (i + 1) - (i + 1)) - 1) * QR
	elif i + 1 > n - (i + 1):
		ans += (abs(n - (i + 1) - (i + 1)) - 1) * QL
	if ans < minn:
		minn = ans
if s * L + QL * (n - 1) < minn:
	minn = s * L + QL * (n - 1)
if s * r + QR * (n - 1) < minn:
	minn = s * r + QR * (n - 1)
print(minn)


(n, l, r, Ql, Qr) = [int(x) for x in input().split(' ')]
w = [int(x) for x in input().split(' ')]
sum = [0 for x in range(n + 1)]
for i in range(1, n + 1):
	sum[i] = sum[i - 1] + w[i - 1]
ans = 2 ** 32
for k in range(0, n + 1):
	temp = sum[k] * l + (sum[n] - sum[k]) * r
	if 2 * k > n:
		temp += (2 * k - n - 1) * Ql
	elif 2 * k < n:
		temp += (n - 2 * k - 1) * Qr
	ans = min(ans, temp)
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.setrecursionlimit(int(pow(10, 6)))
	sys.stdin = open('input.txt', 'r')
except:
	pass
(n, l, r, ql, qr) = L()
w = [0] + L()
for i in range(1, n + 1):
	w[i] += w[i - 1]
s = w[n]
print(min((l * w[i] + r * (s - w[i]) + ql * max(0, 2 * i - n - 1) + qr * max(0, n - 2 * i - 1) for i in range(n + 1))))
endtime = time.time()


(n, l, r, ql, qr) = map(int, input().split())
arr = [int(i) for i in input().split()]
mini = 10 ** 20
sm = sum(arr)
appaji = 0
curr = 0
for i in range(n + 1):
	if i > 0:
		curr += arr[i - 1]
	now = curr * l + (sm - curr) * r
	j = n - i
	if i > j:
		now += (i - j - 1) * ql
	if j > i:
		now += (j - i - 1) * qr
	mini = min(mini, now)
print(mini)


import math
import itertools
(n, L, R, Ql, Qr) = list(map(int, input().split()))
w = list(map(int, input().split()))
pw = list(itertools.accumulate(w))
ts = sum(w)
ans = math.inf
for i in range(n + 1):
	l = i
	r = n - i
	if l > 0:
		lsum = pw[i - 1]
	else:
		lsum = 0
	rsum = ts - lsum
	if l < r:
		ans = min(ans, L * lsum + rsum * R + max((r - l - 1) * Qr, 0))
	else:
		ans = min(ans, L * lsum + rsum * R + max((l - r - 1) * Ql, 0))
print(ans)


(n, l, r, p, q) = map(int, input().split())
arr = list(map(int, input().split()))
(res, s, d) = (int(1 << 62), sum(arr), 0)
for i in range(n + 1):
	if i > 0:
		d += arr[i - 1]
	t = d * l + (s - d) * r
	j = n - i
	if i > j:
		t += (i - j - 1) * p
	if i < j:
		t += (j - i - 1) * q
	res = min(res, t)
print(res)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from math import inf

def main():
	(n, l, r, ql, qr) = [int(x) for x in input().split()]
	weight = [int(x) for x in input().split()]
	preffix = [0] * n
	preffix[0] = weight[0]
	for i in range(1, n):
		preffix[i] = preffix[i - 1] + weight[i]
	suffix = [0] * n
	suffix[n - 1] = weight[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = weight[i] + suffix[i + 1]
	bestAnswer = inf
	for i in range(-1, n):
		leftToRemove = i + 1
		rightToRemove = n - leftToRemove
		if leftToRemove > rightToRemove:
			numOfNotCanceled = max(leftToRemove - rightToRemove - 1, 0)
			total = (preffix[i] if i >= 0 else 0) * l + (suffix[i + 1] if i < n - 1 else 0) * r + numOfNotCanceled * ql
		else:
			numOfNotCanceled = max(rightToRemove - leftToRemove - 1, 0)
			total = (preffix[i] if i >= 0 else 0) * l + (suffix[i + 1] if i < n - 1 else 0) * r + numOfNotCanceled * qr
		bestAnswer = min(bestAnswer, total)
	print(bestAnswer)
BUFFSIZE = 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, BUFFSIZE))
			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, BUFFSIZE))
			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')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


import sys
inf = float('inf')

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, l, r, ql, qr) = get_ints()
Arr = get_array()
pre = [0] * (n + 1)
for i in range(1, n + 1):
	pre[i] = pre[i - 1] + Arr[i - 1]
ans = inf
for i in range(n + 1):
	current_cost = pre[i] * l + (pre[n] - pre[i]) * r
	if i > n - i:
		current_cost += (i - n + i - 1) * ql
	elif i < n - i:
		current_cost += (n - i - i - 1) * qr
	ans = min(ans, current_cost)
print(ans)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
N = 10 ** 5 + 5
(n, l, r, q1, q2) = map(int, input().split())
w = [int(x) for x in input().split()]
pre = [0] * N
for i in range(n):
	pre[i + 1] = pre[i] + w[i]
ans = 10 ** 18
for i in range(n + 1):
	curr = pre[i] * l + (pre[n] - pre[i]) * r
	(x, y) = (i, n - i)
	if x < y:
		curr += q2 * (y - x - 1)
	elif x > y:
		curr += q1 * (x - y - 1)
	ans = min(ans, curr)
print(ans)


from sys import stdin
from itertools import accumulate

def arr_sum(arr):
	return list(accumulate(arr, lambda x, y: x + y))
rints = lambda : [int(x) for x in stdin.readline().split()]
(n, l, r, ql, qr) = rints()
(w, ans) = ([0] + rints(), float('inf'))
mem = arr_sum(w)
for i in range(n + 1):
	(s1, s2) = (mem[i] - mem[0], mem[-1] - mem[i])
	tem = l * s1 + r * s2
	if n - i - i - 1 > 0:
		tem += (n - i - i - 1) * qr
	elif i - (n - i) - 1 > 0:
		tem += (i - (n - i) - 1) * ql
	ans = min(ans, tem)
print(ans)


import time, math as mt, bisect as bs, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * (2 * 10 ** 5 + 5)
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(2 * 10 ** 5 + 5):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return

def readTree(n, e):
	adj = [set() for i in range(n + 1)]
	for i in range(e):
		(u1, u2) = IP()
		adj[u1].add(u2)
	return adj
mod = 10 ** 9 + 7

def solve():
	(n, l, r, ql, qr) = IP()
	li = L()
	pref = [0] + [li[0]] + [0] * (n - 1)
	ans = 1000000000.0
	for i in range(2, len(pref)):
		pref[i] = pref[i - 1] + li[i - 1]
	for i in range(n + 1):
		cost = pref[i] * l + (pref[n] - pref[i]) * r
		(x, y) = (i, n - i)
		if x > y:
			cost += (x - y - 1) * ql
		elif y > x:
			cost += (y - x - 1) * qr
		ans = min(ans, cost)
	print(int(ans))
	return
t = 1
for i in range(t):
	solve()


import sys
from math import log2, floor, ceil, sqrt
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
(n, l, r, ql, qr) = Ri()
a = Ri()
lsumm = [0] * (n + 1)
rsumm = [0] * (n + 1)
ite = 1
for i in range(0, n):
	lsumm[i + 1] = lsumm[i] + a[i]
for i in range(n - 1, -1, -1):
	rsumm[ite] = rsumm[ite - 1] + a[i]
	ite += 1
tans = INF
for i in range(0, n + 1):
	ans = lsumm[i] * l + rsumm[n - i] * r
	if i < n - i:
		ans += (n - i - i - 1) * qr
	elif i > n - i:
		ans += (i - (n - i) - 1) * ql
	tans = min(tans, ans)
print(tans)


import sys
input = sys.stdin.readline
for _ in range(1):
	(n, l, r, ql, qr) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	(temp1, temp2) = ([], [])
	curr = 0
	for i in arr:
		curr += i
		temp1.append(curr)
	curr = 0
	for i in arr[::-1]:
		curr += i
		temp2.append(curr)
	temp2 = temp2[::-1]
	ans = min(l * sum(arr) + (n - 1) * ql, r * sum(arr) + (n - 1) * qr)
	for i in range(n - 1):
		curr = temp1[i] * l + temp2[i + 1] * r
		if i + 1 > n - (i + 1):
			curr += (2 * (i + 1) - n - 1) * ql
		elif i + 1 < n - (i + 1):
			curr += (n - 2 * (i + 1) - 1) * qr
		ans = min(ans, curr)
	print(ans)


(n, l, r, ql, qr) = list(map(int, input().split()))
w = list(map(int, input().split()))
sum = 0
sums = []
for i in range(n):
	sum += w[i]
	sums.append(sum)
min = r * sum + qr * (n - 1)
for i in range(n):
	ss = l * sums[i] + r * (sum - sums[i])
	if i + 1 > n - i - 1 and i - n + i + 1 > 0:
		ss += ql * (i - n + i + 1)
	elif i + 1 < n - i - 1 and n - i - 2 - i > 1:
		ss += qr * (n - i - 2 - i - 1)
	if ss < min:
		min = ss
print(min)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, l, r, ql, qr) = value()
w = array()
ans = inf
tot = sum(w)
cur = w[0]
for i in range(1, n):
	tans = cur * l + (tot - cur) * r
	lefts = i
	rights = n - i
	if lefts > rights + 1:
		extra = lefts - rights - 1
		tans += extra * ql
	if rights > lefts + 1:
		extra = rights - lefts - 1
		tans += extra * qr
	ans = min(ans, tans)
	cur += w[i]
ans = min(ans, tot * l + n * ql - ql, tot * r + n * qr - qr)
print(ans)