You have to restore the wall. The wall consists of $N$ pillars of bricks, the height of the $i$-th pillar is initially equal to $h_{i}$, the height is measured in number of bricks. After the restoration all the $N$ pillars should have equal heights.

You are allowed the following operations: put a brick on top of one pillar, the cost of this operation is $A$; remove a brick from the top of one non-empty pillar, the cost of this operation is $R$; move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is $M$.

You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $0$.

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?


-----Input-----

The first line of input contains four integers $N$, $A$, $R$, $M$ ($1 \le N \le 10^{5}$, $0 \le A, R, M \le 10^{4}$) — the number of pillars and the costs of operations.

The second line contains $N$ integers $h_{i}$ ($0 \le h_{i} \le 10^{9}$) — initial heights of pillars.


-----Output-----

Print one integer — the minimal cost of restoration.


-----Examples-----
Input
3 1 100 100
1 3 8

Output
12

Input
3 100 1 100
1 3 8

Output
9

Input
3 100 100 1
1 3 8

Output
4

Input
5 1 2 4
5 5 3 6 5

Output
4

Input
5 1 2 2
5 5 3 6 5

Output
3

Difficulty: HARD
Tags: Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
(n, a, r, m) = map(int, input().split(' '))
h = list(map(int, input().split(' ')))

def calCost(hi):
	(cnta, cntr) = (0, 0)
	for i in range(len(h)):
		cnta += max(0, hi - h[i])
		cntr += max(0, h[i] - hi)
	if a + r > m:
		return min(cntr, cnta) * m + (cnta - min(cnta, cntr)) * a + (cntr - min(cnta, cntr)) * r
	return cnta * a + cntr * r

def solve():
	(start, end) = (0, max(h))
	while start < end:
		mid = (start + end) // 2
		if calCost(mid) < calCost(mid + 1):
			end = mid
		else:
			start = mid + 1
	return min(calCost(start), calCost(end))
print(solve())


(N, A, R, M) = map(int, input().split())
H = list(map(int, input().split()))

def f(t):
	a = 0
	r = 0
	for h in H:
		r += max(h - t, 0)
		a += max(t - h, 0)
	m = min(a, r)
	return min(a * A + r * R, m * M + A * (a - m) + R * (r - m))
l = min(H)
r = max(H)
while r - l > 3:
	m1 = l + (r - l) // 3
	m2 = r - (r - l) // 3
	if f(m1) > f(m2):
		l = m1
	else:
		r = m2
print(min(f(l), f(l + 1), f(l + 2), f(l + 3)))


(N, A, R, M) = list(map(int, input().split()))
if M > A + R:
	M = A + R
h = list(map(int, input().split()))

def calc(final):
	adds = 0
	removes = 0
	for v in h:
		if v > final:
			removes += v - final
		else:
			adds += final - v
	moves = min(adds, removes)
	return M * moves + A * (adds - moves) + R * (removes - moves)
lo = -1
hi = 10 ** 9 + 1
while hi - lo > 1:
	test = (lo + hi) // 2
	if calc(test) > calc(test + 1):
		lo = test
	else:
		hi = test
print(calc(hi))


import sys
input = sys.stdin.readline

def bin(l, r, c):
	if l == r:
		return l
	m = (l + r + 1) // 2
	if h[m] <= c:
		return bin(m, r, c)
	else:
		return bin(l, m - 1, c)

def cost(c, move):
	res = 0
	i = 0
	if c >= h[-1]:
		i = n - 1
	else:
		i = bin(0, n - 1, c)
	res += a * ((i + 1) * c - H[i + 1])
	res += r * (H[-1] - H[i + 1] - (n - i - 1) * c)
	if move:
		res -= (a + r - m) * min((i + 1) * c - H[i + 1], H[-1] - H[i + 1] - (n - i - 1) * c)
	return res
(n, a, r, m) = list(map(int, input().split()))
h = list(map(int, input().split()))
h.sort()
H = [None] * (n + 1)
H[0] = 0
for i in range(1, n + 1):
	H[i] = H[i - 1] + h[i - 1]
move = m < a + r
if not move:
	print(min((cost(h[i], move) for i in range(n))))
else:
	tt = min(cost(H[-1] // n, move), cost(H[-1] // n + 1, move))
	ttt = min((cost(h[i], move) for i in range(n)))
	print(min(tt, ttt))


import sys

def solve():
	input = sys.stdin.readline
	(N, A, R, M) = map(int, input().split())
	H = [int(h) for h in input().split()]
	H.sort()
	tB = [0] * (N + 1)
	for (i, h) in enumerate(H):
		tB[i + 1] = tB[i] + h
	minCost = 10 ** 20
	for i in range(N):
		toAdd = H[i] * i - tB[i]
		toSub = tB[N] - tB[i + 1] - H[i] * (N - i - 1)
		if M >= A + R:
			minCost = min(minCost, A * toAdd + R * toSub)
		else:
			mN = min(toAdd, toSub)
			minCost = min(minCost, A * (toAdd - mN) + R * (toSub - mN) + M * mN)
	if M < A + R:
		sumH = sum(H)
		lcost = 0
		hcost = 0
		fH = sumH // N
		for (i, h) in enumerate(H):
			if h < fH:
				lcost += (fH - h) * M
			if h > fH + 1:
				hcost += (h - fH - 1) * M
		lcost += sumH % N * R
		hcost += (N - sumH % N) * A
		minCost = min(minCost, lcost)
		minCost = min(minCost, hcost)
	print(minCost)
	return 0
solve()


import io
import os
from bisect import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

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

def oint():
	return int(input())

def find_lu_value(th):
	hi = bisect(h, th) - 1
	lv = th * (hi + 1) - ps[hi]
	uv = ps[n - 1] - ps[hi] - (n - 1 - hi) * th
	return (lv, uv)

def calc_cost(th):
	cost = 0
	(l, u) = find_lu_value(th)
	if l > u:
		cost += u * m + (l - u) * a
	else:
		cost += l * m + (u - l) * r
	return cost

def calc_prefixsum(h):
	ps = [h[0]]
	for i in range(1, n):
		ps.append(h[i] + ps[-1])
	return ps
(n, a, r, m) = rint()
h = list(rint())
m = min(m, a + r)
h.sort()
ps = calc_prefixsum(h)
ans = 10 ** 99
lv = h[0]
rv = h[-1]
ans = min(ans, calc_cost(lv), calc_cost(rv), calc_cost(lv + 1))
while rv - lv >= 2:
	mv = (rv - lv) // 2 + lv
	mc = calc_cost(mv)
	rc = calc_cost(mv + 1)
	ans = min(ans, rc, mc)
	if mc < rc:
		rv = mv
	elif mc > rc:
		lv = mv
print(ans)


import sys
import math
import bisect

def query_value(A, a, r, m, target):
	n = len(A)
	more_val = 0
	less_val = 0
	for i in range(n):
		if A[i] > target:
			more_val += A[i] - target
		elif A[i] < target:
			less_val += target - A[i]
	move_val = min(more_val, less_val)
	val1 = more_val * r + less_val * a
	val2 = (more_val - move_val) * r + (less_val - move_val) * a + move_val * m
	return min(val1, val2)

def main():
	(n, a, r, m) = map(int, input().split())
	A = list(map(int, input().split()))
	left = min(A)
	right = max(A)
	while right - left > 2:
		m1 = left + (right - left) // 3
		m2 = left + (right - left) // 3 * 2
		val1 = query_value(A, a, r, m, m1)
		val2 = query_value(A, a, r, m, m2)
		if val1 <= val2:
			right = m2
		else:
			left = m1
	B = []
	for i in range(left, right + 1):
		val = query_value(A, a, r, m, i)
		B.append(val)
	print(min(B))
main()


def cost(arr, target, a, r, m):
	c_add = 0
	c_rem = 0
	for hi in arr:
		if hi > target:
			c_rem += hi - target
		else:
			c_add += target - hi
	move_amount = min(c_add, c_rem)
	with_m = move_amount * m + (c_add - move_amount) * a + (c_rem - move_amount) * r
	wout_m = c_add * a + c_rem * r
	return min(with_m, wout_m)
(n, a, r, m) = map(int, input().split())
h = list(map(int, input().split()))
le = min(h)
ri = max(h)
while ri > le + 10:
	mid = (le + ri) // 2
	cm = cost(h, mid, a, r, m)
	cn = cost(h, mid + 1, a, r, m)
	if cn <= cm:
		le = mid + 1
	else:
		ri = mid
print(min([cost(h, tar, a, r, m) for tar in range(le, ri + 1)]))


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

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

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
(n, a, r, m) = li()
l = sorted(li())
cnt1 = [0]
for i in l:
	cnt1.append(cnt1[-1] + i)
cnt2 = [0]
for i in l[::-1]:
	cnt2.append(cnt2[-1] + i)
cnt2 = cnt2[::-1]

def give(s):
	leftind = bl(l, s)
	rightind = br(l, s)
	a = leftind * s - cnt1[leftind]
	b = cnt2[rightind] - (len(l) - rightind) * s
	return [a, b]

def cost(s, b):
	temp = min(b, s)
	return temp * m + (b - temp) * r + (s - temp) * a

def binary():
	ans = float('inf')
	left = 0
	right = 10 ** 18
	while left <= right:
		mid = left + right >> 1
		(s1, b1) = give(mid)
		(s2, b2) = give(mid + 1)
		if cost(s1, b1) < cost(s2, b2):
			ans = min(ans, cost(s1, b1))
			right = mid - 1
		else:
			ans = min(ans, cost(s2, b2))
			left = mid + 1
	return ans
m = min(m, a + r)
print(binary())


import sys

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, ad, rm, mv) = MAP()
A = LIST()

def check(m):
	adcnt = rmcnt = 0
	for a in A:
		if a < m:
			adcnt += m - a
		elif a > m:
			rmcnt += a - m
	diff = adcnt - rmcnt
	if diff >= 0:
		return rmcnt * min(ad + rm, mv) + diff * ad
	else:
		return adcnt * min(ad + rm, mv) + -diff * rm
A.sort()
low = -1
hi = 10 ** 9 + 1
while low + 2 < hi:
	m1 = (low * 2 + hi) // 3
	m2 = (low + hi * 2) // 3
	res1 = check(m1)
	res2 = check(m2)
	if res1 <= res2:
		hi = m2
	else:
		low = m1
ans = min(res1, res2)
print(ans)


from collections import defaultdict
from random import randint
itl = lambda : list(map(int, input().strip().split()))

class Problem:

	def read(self):
		(self.N, self.A, self.R, self.M) = itl()
		self.pillars = itl()
		self.lo = min(self.pillars)
		self.hi = max(self.pillars)

	def solve(self):
		lo = self.lo
		hi = self.hi
		while lo <= hi:
			mid = lo + hi >> 1
			left = self.cost(mid - 1)
			center = self.cost(mid)
			right = self.cost(mid + 1)
			if center < right and center < left:
				return center
			assert left >= center >= right or left <= center <= right
			if right > left:
				hi = mid - 1
			else:
				lo = mid + 1
		return self.cost(lo)

	def cost(self, target):
		below = 0
		above = 0
		for p in self.pillars:
			if p < target:
				below += target - p
			elif p > target:
				above += p - target
		option1 = self.A * below + self.R * above
		option2 = self.M * min(below, above) + abs(below - above) * (self.A if below > above else self.R)
		return min(option1, option2)

	def bruteforce(self):
		ans = float('inf')
		for target in range(min(self.pillars), max(self.pillars) + 1):
			cost = self.cost(target)
			print(target, cost)
			ans = min(ans, cost)
		return ans
P = Problem()
P.read()
print(P.solve())


import sys
input = sys.stdin.readline
(N, A, R, M) = map(int, input().split())
al = list(map(int, input().split()))
x0 = 0
x1 = 1
x2 = 3
x3 = max(al)

def check(x):
	a = 0
	r = 0
	for z in al:
		if x > z:
			a += x - z
		else:
			r += z - x
	if M < A + R:
		m = min(a, r)
		return (a - m) * A + (r - m) * R + m * M
	return a * A + r * R
while x3 - x0 > 2:
	x1 = (x0 * 2 + x3) // 3
	x2 = (x0 + x3 * 2) // 3
	if check(x1) <= check(x2):
		x3 = x2
	else:
		x0 = x1
res = float('inf')
for i in range(x0, x3 + 1):
	res = min(res, check(i))
print(res)


import sys
import math
import itertools
from collections import deque
(n, a, r, m) = map(int, input().split())
m = min(m, a + r)
h = list(map(int, input().split()))
low = 0
high = 0

def cost(he):
	add = 0
	remov = 0
	for num in h:
		if num < he:
			add += he - num
		else:
			remov += num - he
	need = abs(add - remov)
	if add > remov:
		need *= a
	else:
		need *= r
	return min(add, remov) * m + need
for num in h:
	high = max(high, num)
while low < high:
	mid = low + high >> 1
	mid2 = mid + 1
	val1 = cost(mid)
	val2 = cost(mid2)
	if val1 <= val2:
		high = mid
	else:
		low = mid + 1
ans = cost(low)
print(ans)


def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split(' ')))
(n, a, r, m) = read_ints()
h = list(read_ints())
h.sort()
lo = h[0]
hi = h[-1]
s = [0]
for i in h:
	s.append(s[-1] + i)
ans = int(1e+20)
for i in range(n):
	target = h[i]
	inc = i * target - s[i]
	dec = s[n] - s[i + 1] - (n - i - 1) * target
	plan_a = inc * a + dec * r
	plan_b = (inc - dec) * a + dec * m if inc >= dec else inc * m + (dec - inc) * r
	ans = min(ans, min(plan_a, plan_b))
avg = s[n] // n
for target in range(max(0, avg - 1), avg + 2):
	inc = 0
	dec = 0
	for i in h:
		if i > target:
			dec += i - target
		else:
			inc += target - i
	plan_a = inc * a + dec * r
	plan_b = (inc - dec) * a + dec * m if inc >= dec else inc * m + (dec - inc) * r
	ans = min(ans, min(plan_a, plan_b))
print(ans)


import sys
input = sys.stdin.readline
(N, A, R, M) = map(int, input().split())
H = list(map(int, input().split()))

def get(l):
	over = 0
	under = 0
	for h in H:
		if h > l:
			over += h - l
		else:
			under += l - h
	if A + R <= M:
		return over * R + under * A
	elif over < under:
		return over * M + (under - over) * A
	else:
		return under * M + (over - under) * R
l1 = -1
l2 = 10 ** 9 + 1
ans = 10 ** 18
while 2 < l2 - l1:
	m1 = (2 * l1 + l2) // 3
	m2 = (l1 + 2 * l2) // 3
	s_m1 = get(m1)
	s_m2 = get(m2)
	ans = min(ans, s_m1)
	ans = min(ans, s_m2)
	if s_m1 >= s_m2:
		l1 = m1
	else:
		l2 = m2
for i in range(l1 - 5, l2 + 5):
	ans = min(ans, get(i))
print(ans)


import sys
import bisect
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	(n, a, r, m) = nm()
	hl = nl()
	shl = [0] * (n + 1)
	hl.sort()
	for i in range(n):
		shl[i + 1] = shl[i] + hl[i]

	def cost(x):
		lidx = bisect.bisect_left(hl, x)
		ridx = bisect.bisect_right(hl, x)
		much = shl[-1] - shl[ridx] - x * (n - ridx)
		less = x * lidx - shl[lidx]
		res = min(m, a + r) * min(much, less)
		if much > less:
			res += r * (much - less)
		else:
			res += a * (less - much)
		return res
	(lo, hi) = (min(hl) - 1, max(hl) + 1)
	while hi - lo > 3:
		mlo = (hi + lo * 2) // 3
		mhi = (hi * 2 + lo) // 3
		if cost(mlo) < cost(mhi):
			hi = mhi
		else:
			lo = mlo
	print(min((cost(i) for i in range(lo, hi + 1))))
	return
solve()


import bisect

def solve(H, heights, pref, N):
	pos = bisect.bisect_left(heights, H)
	res = 0
	k1 = H * pos - pref[pos]
	k2 = pref[N] - pref[pos] - H * (N - pos)
	res = min(k1, k2)
	k1 -= res
	k2 -= res
	res *= M
	res += k1 * A
	res += k2 * R
	return res
(N, A, R, M) = list(map(int, input().split()))
heights = list(map(int, input().split()))
M = min(M, A + R)
heights = sorted(heights)
pref = [0 for i in range(N + 1)]
for i in range(N):
	pref[i + 1] = pref[i] + heights[i]
b1 = pref[N] // N
b2 = b1 + 1
ans = 10 ** 25
s1 = solve(b1, heights, pref, N)
s2 = solve(b2, heights, pref, N)
ans = min([s1, s2, ans])
for i in range(N):
	bi = heights[i]
	ans = min(ans, solve(bi, heights, pref, N))
print(ans)


import bisect

def func(val):
	cost = 0
	(toAdd, toRemove) = (0, 0)
	lessEqual = bisect.bisect_right(arr, val)
	greater = n - lessEqual
	toAdd = lessEqual * val - dp[lessEqual]
	toRemove = total - dp[lessEqual] - greater * val
	if toRemove >= toAdd:
		confirmRemove = toRemove - toAdd
		toRemove = toAdd
		cost += confirmRemove * R
		cost += min(toAdd * A + R * toRemove, toAdd * M)
	else:
		confirmAdd = toAdd - toRemove
		cost += confirmAdd * A
		toAdd = toRemove
		cost += min(toAdd * A + R * toRemove, toAdd * M)
	return cost
(n, A, R, M) = map(int, input().split())
arr = sorted([int(x) for x in input().split()])
dp = [0]
for item in arr:
	dp.append(dp[-1] + item)
total = sum(arr)
ans = R * total
avg = total // n
heightsToCheck = arr + [avg, avg + 1]
cost = min([func(h) for h in heightsToCheck])
print(min(ans, cost))


(n, add, remove, move) = [int(i) for i in input().split()]
heights = [int(i) for i in input().split()]

def cost_for_this_height(h, heights, n, add, remove, move):
	above = 0
	below = 0
	for i in range(n):
		if heights[i] > h:
			above += heights[i] - h
		elif heights[i] < h:
			below += h - heights[i]
	if above >= below:
		if move <= add + remove:
			cost = below * move + (above - below) * remove
		else:
			cost = below * (add + remove) + (above - below) * remove
	elif move <= add + remove:
		cost = above * move + (below - above) * add
	else:
		cost = above * (add + remove) + (below - above) * add
	return cost
left = min(heights) - 2
right = max(heights) + 2
while True:
	x = int((left + right) / 2)
	cost_mid = cost_for_this_height(x, heights, n, add, remove, move)
	cost_prev = cost_for_this_height(x - 1, heights, n, add, remove, move)
	cost_next = cost_for_this_height(x + 1, heights, n, add, remove, move)
	if cost_prev >= cost_mid and cost_next >= cost_mid:
		print(cost_mid)
		break
	elif cost_prev >= cost_mid >= cost_next:
		left = x
	else:
		right = x
	if right == left:
		print(cost_mid)
		break


from bisect import bisect_left
from itertools import accumulate
import sys

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

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

def main():
	(n, a, r, m) = MI()
	if a + r < m:
		m = a + r
	hh = LI()
	hh.sort()
	cs = [h for h in accumulate(hh)]

	def cost(m1):
		i = bisect_left(hh, m1)
		less = cs[i - 1] if i else 0
		ca = i * m1 - less
		cr = cs[-1] - less - (n - i) * m1
		move = min(ca, cr)
		return move * m + max(0, ca - move) * a + max(0, cr - move) * r
	L = -1
	R = hh[-1] + 1
	while L + 2 < R:
		m1 = (L * 2 + R) // 3
		m2 = (L + R * 2) // 3
		c1 = cost(m1)
		c2 = cost(m2)
		if c1 < c2:
			R = m2
		else:
			L = m1
	print(min(cost(L), cost(R), cost((L + R) // 2)))
main()


def f(h):
	numofh = 0
	numofl = 0
	for i in li:
		if i < h:
			numofl += h - i
		else:
			numofh += i - h
	if numofh > numofl:
		return m * numofl + (numofh - numofl) * r
	else:
		return m * numofh + (numofl - numofh) * a

def binary_search(low, high):
	if low > high:
		return
	mid = (low + high) // 2
	if f(mid - 1) < f(mid):
		return binary_search(low, mid - 1)
	if f(mid + 1) < f(mid):
		return binary_search(mid + 1, high)
	return mid
(n, a, r, m) = map(int, input().split())
l = input().split()
li = [int(i) for i in l]
m = min(a + r, m)
print(f(binary_search(0, 10 ** 10)))


import io
import os
from bisect import bisect_left, bisect_right

def minimize(f, lo, hi):
	assert lo <= hi
	while hi - lo >= 3:
		mid1 = lo + (hi - lo) // 3
		mid2 = hi - (hi - lo) // 3
		if False:
			indices = [lo, mid1, mid2, hi]
			values = [f(x) for x in indices]
			deltas = [y - x for (x, y) in zip(values, values[1:])]
			print(indices)
			print(values)
			print(['>' if 0 > d else '<' if 0 < d else '=' for d in deltas])
			print()
		delta = f(mid2) - f(mid1)
		if delta < 0:
			lo = mid1
		else:
			assert delta >= 0
			hi = mid2
	return min((f(x) for x in range(lo, hi + 1)))

def solve(N, A, R, M, H):
	H.sort()
	pref = [0]
	for x in H:
		pref.append(pref[-1] + x)

	def rangeSum(i, j):
		return pref[j] - pref[i]
	M = min(M, A + R)

	def getCost(h):
		i = bisect_left(H, h)
		j = bisect_right(H, h)
		lt = h * (i - 0) - rangeSum(0, i)
		gt = rangeSum(j, N) - h * (N - j)
		numM = min(lt, gt)
		numA = lt - numM
		numR = gt - numM
		return numA * A + numR * R + numM * M
	lo = 0
	hi = H[-1]
	return minimize(getCost, lo, hi)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, A, R, M) = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
ans = solve(N, A, R, M, H)
print(ans)


import sys
from copy import copy
input = sys.stdin.readline

def find(l, ile):
	pocz = 0
	kon = len(l) - 1
	while pocz + 1 < kon:
		mid = (pocz + kon) // 2
		if l[mid] < ile:
			pocz = mid
		else:
			kon = mid
	return pocz

def solve(l, sumpref, ile, A, R, M):
	pos = find(l, ile)
	dol = ile * (pos + 1) - sumpref[pos]
	gora = sumpref[-1] - sumpref[pos] - ile * (len(l) - pos - 1)
	m = min(dol, gora)
	return min(dol * A + gora * R, (dol - m) * A + (gora - m) * R + m * M)
(n, A, R, M) = [int(a) for a in input().split()]
l = [int(a) for a in input().split()]
l.sort()
pocz = l[0]
kon = l[-1]
sumpref = l.copy()
for i in range(1, len(sumpref)):
	sumpref[i] += sumpref[i - 1]
while pocz + 6 < kon:
	x = (2 * pocz + kon) // 3
	y = (pocz + 2 * kon) // 3
	s = [solve(l, sumpref, lol, A, R, M) for lol in [pocz, x, y, kon]]
	ms = min(s)
	if s[0] == ms or s[1] == ms:
		kon = y
	else:
		pocz = x
print(min([solve(l, sumpref, lol, A, R, M) for lol in range(pocz, kon + 1)]))


import sys

def check(t):
	(na, nr) = (0, 0)
	for h in p:
		if h < t:
			na += t - h
		else:
			nr += h - t
	m = min(na, nr)
	return min(m * M + A * (na - m) + R * (nr - m), na * A + nr * R)
(N, A, R, M) = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))
ans = float('inf')
(lo, hi) = (min(p), max(p))
while lo <= hi:
	mid = (lo + hi) // 2
	(a, b) = (check(mid), check(mid + 1))
	if a <= b:
		hi = mid - 1
		ans = min(ans, a)
	else:
		lo = mid + 1
print(ans)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List
(N, A, R, M) = map(int, input().split())
H = [int(x) for x in input().split()]
M = min(A + R, M)
H.sort()
ans = float('inf')
presum = [0]
for h in H:
	presum.append(presum[-1] + h)

def cal(height, hi=-1):
	i = bisect.bisect_right(H, height) if hi < 0 else hi
	p = height * i - presum[i]
	q = presum[-1] - presum[i] - (N - i) * height
	if p >= q:
		return A * (p - q) + M * q
	else:
		return R * (q - p) + M * p
ans = min(cal(presum[-1] // N), cal(presum[-1] // N + 1))
ans = min(ans, min([cal(h, i) for (i, h) in enumerate(H)]))
print(ans)


def calc(h):
	lo = hi = 0
	for cur in arr:
		if cur < h:
			lo += h - cur
		else:
			hi += cur - h
	return m * min(lo, hi) + ((hi - lo) * r if hi >= lo else (lo - hi) * a)

def solve():
	(le, ri) = (0, 5 + 10 ** 9)
	while le + 50 < ri:
		(g, h) = (le + (ri - le) // 3, le + 2 * (ri - le) // 3)
		if calc(g) < calc(h):
			ri = h
		else:
			le = g
	ret = calc(le)
	for i in range(le, ri + 5):
		ret = min(ret, calc(i))
	return ret
(n, a, r, m) = map(int, input().split())
arr = list(map(int, input().split()))
m = min(m, a + r)
print(solve())


from sys import stdin
from collections import Counter, deque
input = stdin.buffer.readline
(n, a, r, m) = map(int, input().split())
ls = list(map(int, input().split()))

def get_cost(h):
	(cc, ca, cr) = (0, 0, 0)
	for u in ls:
		if u < h:
			ca += h - u
		elif u > h:
			cr += u - h
	if m < a + r:
		mn = min(ca, cr)
		cc += mn * m
		ca -= mn
		cr -= mn
	cc += ca * a + cr * r
	return cc
(lo, hi) = (0.0, 1000000000.0)
while abs(hi - lo) > 1.0:
	(m1, m2) = (lo + (hi - lo) / 3, hi - (hi - lo) / 3)
	(cm1, cm2) = (get_cost(int(m1)), get_cost(int(m2)))
	if cm1 >= cm2:
		lo = m1
	else:
		hi = m2
lo = int(lo)
mn = min([get_cost(max(h, 0)) for h in (lo - 1, lo, lo + 1)])
print(mn)


from __future__ import division, print_function
import itertools
import sys
if sys.version_info[0] < 3:
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def give_it_all():
	if sys.version_info[0] < 3:
		os.write(1, out.build())
	else:
		os.write(1, out.build().encode())

def result_out(*args):
	for arg in args:
		out.append(arg)
		out.append(' ')
	out.append('\n')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def input1(type=int):
	return type(input())

def input2(type=int):
	[a, b] = list(map(type, input().split()))
	return (a, b)

def input3(type=int):
	[a, b, c] = list(map(type, input().split()))
	return (a, b, c)

def input_array(type=int):
	return list(map(type, input().split()))

def input_string():
	s = input()
	return list(s)

def solve(h, arr, a, r, m):
	rgt = len(arr) - 1
	while rgt >= 0 and arr[rgt] <= h:
		rgt -= 1
	i = 0
	res = 0
	while i < len(arr):
		if arr[i] < h:
			if rgt != -1 and m <= a + r:
				nw = min(h - arr[i], arr[rgt] - h)
				res += nw * m
				arr[rgt] -= nw
				arr[i] += nw
				if arr[rgt] == h:
					rgt -= 1
			else:
				res += (h - arr[i]) * a
				arr[i] = h
		elif arr[i] > h:
			res += (arr[i] - h) * r
			arr[i] = h
		while rgt >= 0 and arr[rgt] <= h:
			rgt -= 1
		if arr[i] == h:
			i += 1
	return res

def main():
	[n, a, r, m] = input_array()
	arr = input_array()
	arr.sort()
	solve(7, arr.copy(), a, r, m)
	low = -1
	high = max(arr)
	while high - low > 1:
		mid = high + low >> 1
		if solve(mid, arr.copy(), a, r, m) < solve(mid + 1, arr.copy(), a, r, m):
			high = mid
		else:
			low = mid
	print(solve(low + 1, arr.copy(), a, r, m))
	pass
main()


import sys, bisect
input = sys.stdin.buffer.readline
(n, A, R, M) = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
b = []
tmp = 0
for e in h:
	tmp += e
	b.append(tmp)

def f(x):
	k = bisect.bisect_left(h, x)
	if k == 0:
		plus = 0
		mns = b[-1] - n * x
	else:
		plus = k * x - b[k - 1]
		mns = b[-1] - b[k - 1] - (n - k) * x
	if mns <= plus:
		return mns * M + (plus - mns) * A
	return plus * M + (mns - plus) * R
if A + R <= M:
	(bef, aft) = (0, sum(h))
	res = aft * R
	for i in range(n):
		res = min(res, (i * h[i] - bef) * A + (aft - (n - i) * h[i]) * R)
		bef += h[i]
		aft -= h[i]
	print(res)
else:
	high = 10 ** 9
	low = 0
	while high - low > 5:
		mid_left = high // 3 + low * 2 // 3
		mid_right = high * 2 // 3 + low // 3
		if f(mid_left) >= f(mid_right):
			low = mid_left
		else:
			high = mid_right
	res = b[-1] * R
	for i in range(low, high + 1):
		res = min(res, f(i))
	print(res)


def solve_for_height(n, add_cost, remove_cost, move_cost, current_height, heights, cum_heights):
	lo = 1
	hi = n
	while lo <= hi:
		mid = (lo + hi) // 2
		if heights[mid] <= current_height:
			lo = mid + 1
		else:
			hi = mid - 1
	add = (lo - 1) * current_height - cum_heights[lo - 1]
	remove = cum_heights[n] - cum_heights[lo - 1] - (n - lo + 1) * current_height
	if add > remove:
		ans = (add - remove) * add_cost + remove * move_cost
	else:
		ans = (remove - add) * remove_cost + add * move_cost
	return ans

def main():
	(n, add_cost, remove_cost, move_cost) = map(int, input().split())
	move_cost = min(add_cost + remove_cost, move_cost)
	heights = [int(h) for h in input().split()]
	heights.sort()
	heights.insert(0, 0)
	cum_heights = [0]
	for index in range(1, n + 1):
		cum_heights.append(cum_heights[index - 1] + heights[index])
	lo = 0
	hi = heights[n]
	ans = cum_heights[n] * remove_cost
	while lo <= hi:
		mid1 = (lo + lo + hi) // 3
		mid2 = (lo + hi + hi) // 3
		cost1 = solve_for_height(n, add_cost, remove_cost, move_cost, mid1, heights, cum_heights)
		cost2 = solve_for_height(n, add_cost, remove_cost, move_cost, mid2, heights, cum_heights)
		ans = min(ans, min(cost1, cost2))
		if cost1 < cost2:
			hi = mid2 - 1
		else:
			lo = mid1 + 1
	print(ans)
main()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def f(x):
	ind = bisect_right(h, x)
	small = ind * x - pre[ind]
	big = pre[-1] - pre[ind] - (n - ind) * x
	if big >= small:
		cur = small * m + r * (big - small)
	else:
		cur = big * m + (small - big) * a
	return cur
t = 1
for i in range(t):
	(n, a, r, m) = RL()
	h = RLL()
	h.sort()
	mi = h[0]
	ma = h[-1]
	m = min(m, r + a)
	pre = [0]
	for x in h:
		pre.append(pre[-1] + x)
	while mi + 3 < ma:
		mid = (mi + ma) // 2
		f1 = f(mid - 1)
		f2 = f(mid + 1)
		if f1 <= f2:
			ma = mid + 1
		else:
			mi = mid - 1
	ans = min((f(x) for x in range(mi, ma + 1)))
	print(ans)


from itertools import accumulate
from bisect import bisect_right, bisect_left

def f(x):
	i = bisect_right(h, x)
	over = sm - acc[i] - x * (n - i)
	j = bisect_left(h, x)
	under = x * j - acc[j]
	if a + r > m:
		move = min(under, over)
		under -= move
		over -= move
		ret = m * move + a * under + r * over
	else:
		ret = a * under + r * over
	return ret
(n, a, r, m) = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
acc = [0] + list(accumulate(h))
sm = sum(h)
lb = 0
ub = 10 ** 9
for _ in range(100):
	tl = (2 * lb + ub) // 3
	tr = (lb + 2 * ub) // 3
	if f(tl) >= f(tr):
		lb = tl
	else:
		ub = tr
ans = 10 ** 18
for i in range(max(lb - 10, 0), min(ub + 10, 10 ** 9 + 1)):
	ans = min(ans, f(i))
print(ans)


from bisect import bisect_left, bisect_right
from collections import Counter
from sys import stdin
input = stdin.readline
(n, a, r, m) = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
c = Counter(arr)
cl = list(c.items())
cl.sort()
s = sum(arr)
cs = 0
cc = 0
ccl = [[cl[0][1], cl[0][1] * cl[0][0]]]
for i in range(1, len(cl)):
	ccl.append([ccl[-1][0] + cl[i][1], ccl[-1][1] + cl[i][0] * cl[i][1]])
ccl.append([0, 0])
ans = float('inf')

def calcVal(cv):
	i = bisect_left(cl, (cv, 0))
	rs = s - ccl[i - 1][1] - c[cv] * cv
	es = rs - (n - c[cv] - ccl[i - 1][0]) * cv
	ss = ccl[i - 1][0] * cv - ccl[i - 1][1]
	if a + r > m:
		si = min(es, ss)
		ca = si * m + (ss - si) * a + (es - si) * r
	else:
		ca = ss * a + es * r
	return ca
start = cl[0][0]
end = cl[-1][0]
while start < end:
	middle = (start + end) // 2
	(m1v, mv, m2v) = (calcVal(middle - 1), calcVal(middle), calcVal(middle + 1))
	if mv <= m1v and mv <= m2v:
		start = middle
		break
	if m1v > m2v:
		start = middle + 1
	else:
		end = middle
print(calcVal(start))


(N, A, R, M) = map(int, input().split())
h = list(map(int, input().split()))
if A * R == 0:
	print(0)
	return
if M > A + R:

	def condition(num):
		test = 0
		for i in range(N):
			if num > h[i]:
				test += A
			else:
				test -= R
		return 0 >= test
	start = 1
	end = 10 ** 10
	while end - start > 1:
		test = (end + start) // 2
		if condition(test):
			start = test
		else:
			end = test
	if condition(end):
		ans = 0
		for i in range(N):
			if end > h[i]:
				ans += A * (end - h[i])
			else:
				ans += R * (h[i] - end)
		print(ans)
	elif condition(start):
		ans = 0
		for i in range(N):
			if start > h[i]:
				ans += A * (start - h[i])
			else:
				ans += R * (h[i] - start)
		print(ans)
	else:
		print(R * sum(h))
else:
	H = sum(h)
	q = H // N
	test1 = 0

	def condition1(num):
		count = 0
		for i in range(N):
			count += int(h[i] < num)
		return 0 >= M * count - R * N
	start = 1
	end = q
	while end - start > 1:
		test = (end + start) // 2
		if condition1(test):
			start = test
		else:
			end = test
	if condition1(end):
		for i in range(N):
			if end > h[i]:
				test1 += M * (end - h[i])
		test1 += R * (H - N * end)
	elif condition1(start):
		for i in range(N):
			if start > h[i]:
				test1 += M * (start - h[i])
		test1 += R * (H - N * start)
	else:
		test1 = H * R
	test2 = 0

	def condition2(num):
		count = 0
		for i in range(N):
			count += int(h[i] > num)
		return 0 >= count * M - A * N
	start = q + 1
	end = max(h) - 1
	while end - start > 1:
		test = (end + start) // 2
		if condition2(test):
			end = test
		else:
			start = test
	if condition2(start):
		for i in range(N):
			if h[i] >= start:
				test2 += M * (h[i] - start)
		test2 += A * (N * start - H)
	elif condition2(end):
		for i in range(N):
			if h[i] >= end:
				test2 += M * (h[i] - end)
		test2 += A * (N * end - H)
	else:
		test2 = A * (N * max(h) - H)
	print(min(test1, test2))


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

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

def RequiredMoney(h):
	bricks_need = 0
	bricks_have = 0
	money = 0
	for i in range(n):
		if height[i] > h:
			bricks_have += height[i] - h
		elif height[i] < h:
			bricks_need += h - height[i]
	if a + r <= m:
		money = bricks_have * r + bricks_need * a
	else:
		bricks = min(bricks_have, bricks_need)
		bricks_have -= bricks
		bricks_need -= bricks
		money = bricks * m + bricks_need * a + bricks_have * r
	return money
(n, a, r, m) = value()
height = array()
low = 0
high = max(height)
while low <= high:
	mid1 = low + (high - low) // 3
	mid2 = high - (high - low) // 3
	if RequiredMoney(mid1) <= RequiredMoney(mid2):
		high = mid2 - 1
	else:
		low = mid1 + 1
print(RequiredMoney(low))


(n, a, r, m) = [int(x) for x in input().split()]
height = [int(x) for x in input().split()]
hmax = max(height)
height.sort()

def tellCost(h):
	cost = 0
	(add, remove) = (0, 0)
	for i in range(n):
		if h > height[i]:
			add += abs(h - height[i])
		else:
			remove += abs(h - height[i])
	move = min(remove, add)
	if a + r >= m:
		cost += m * move
		if add > remove:
			cost += abs(add - remove) * a
		else:
			cost += abs(add - remove) * r
	else:
		cost += add * a
		cost += remove * r
	return cost
(s, e) = (0, hmax)
while s < e:
	mid = (s + e) // 2
	(cost1, cost2) = (tellCost(mid), tellCost(mid + 1))
	if cost2 > cost1:
		e = mid
	else:
		s = mid + 1
print(tellCost(s))


import sys
input = sys.stdin.readline
from itertools import accumulate
import bisect
(N, A, R, M) = list(map(int, input().split()))
W = sorted(map(int, input().split()))
SUM = list(accumulate(W))
SW = SUM[-1]
indmin = 0
indmax = 1
ANS = 1 << 62

def calc(MINUS, PLUS, A, R, M):
	RET1 = MINUS * A + PLUS * R
	MIN = min(MINUS, PLUS)
	RET2 = MIN * M + (MINUS - MIN) * A + (PLUS - MIN) * R
	return min(RET1, RET2)
while indmin < N:
	while indmax < N and W[indmax] == W[indmin]:
		indmax += 1
	ave = W[indmin]
	MINUS = ave * (indmin + 1) - SUM[indmin]
	PLUS = SW - SUM[indmax - 1] - ave * (N - indmax)
	ANS = min(ANS, calc(MINUS, PLUS, A, R, M))
	indmin = indmax
	indmax += 1
AVE = SW // N
for ave in range(max(W[0], AVE - 10 ** 4), min(AVE + 10 ** 4, W[-1])):
	indmin = bisect.bisect_left(W, ave)
	if W[indmin] == ave:
		continue
	(indmin, indmax) = (indmin - 1, indmin)
	MINUS = ave * (indmin + 1) - SUM[indmin]
	PLUS = SW - SUM[indmax - 1] - ave * (N - indmax)
	ANS = min(ANS, calc(MINUS, PLUS, A, R, M))
print(ANS)


(n, a, r, m) = map(int, input().split())
h = list(map(int, input().split()))
m = min(m, a + r)

def get(M):
	up = 0
	dw = 0
	for e in h:
		if e > M:
			up += e - M
		else:
			dw += M - e
	ans = m * min(dw, up)
	if dw > up:
		ans += (dw - up) * a
	else:
		ans += (up - dw) * r
	return ans
L = 0
R = int(1000000000.0)
mn = int(1e+18)
while R - L > 10:
	M1 = L + (R - L) // 3
	M2 = R - (R - L) // 3
	V1 = get(M1)
	V2 = get(M2)
	mn = min(mn, V1)
	mn = min(mn, V2)
	if V1 < V2:
		R = M2
	elif V2 < V1:
		L = M1
	else:
		L = M1
		R = M2
for it in range(L, R + 1):
	mn = min(mn, get(it))
print(mn)


from sys import stdin, stdout
(N, A, R, M) = map(int, stdin.readline().split())
ha = list(map(int, stdin.readline().split()))

def calc(v, ha, A, R, M):
	a = 0
	r = 0
	for h in ha:
		a += max(v - h, 0)
		r += max(h - v, 0)
	m = min(a, r)
	return min(a * A + r * R, m * M + (a - m) * A + (r - m) * R)

def restorer_distance(N, A, R, M, ha):
	l = min(ha)
	r = max(ha)
	lans = 0
	rans = 0
	while l < r:
		lm = l + (r - l) // 3
		rm = r - (r - l) // 3
		lans = calc(lm, ha, A, R, M)
		rans = calc(rm, ha, A, R, M)
		if lans <= rans:
			r = rm - 1
		else:
			l = lm + 1
	return min(lans, rans)
stdout.write(str(restorer_distance(N, A, R, M, ha)) + '\n')


def solve():
	(N, A, R, M) = map(int, input().split())
	H = sorted(list(map(int, input().split())))
	tB = [0] * (N + 1)
	minCost = 10 ** 20
	for (i, h) in enumerate(H):
		tB[i + 1] = tB[i] + h
	for i in range(N):
		toAdd = H[i] * i - tB[i]
		toSub = tB[N] - tB[i + 1] - H[i] * (N - i - 1)
		if M >= A + R:
			minCost = min(minCost, A * toAdd + R * toSub)
		else:
			mN = min(toAdd, toSub)
			minCost = min(minCost, A * (toAdd - mN) + R * (toSub - mN) + M * mN)
	if M < A + R:
		sumH = sum(H)
		(lcost, hcost) = (0, 0)
		fH = sumH // N
		for (i, h) in enumerate(H):
			if h < fH:
				lcost += (fH - h) * M
			if h > fH + 1:
				hcost += (h - fH - 1) * M
		lcost += sumH % N * R
		hcost += (N - sumH % N) * A
		minCost = min(minCost, lcost, hcost)
	print(minCost)
solve()


import sys
input = sys.stdin.readline

def compress(string):
	string.append(-1)
	n = len(string)
	(begin, end, cnt) = (0, 1, 1)
	ans = []
	while end < n:
		if string[begin] == string[end]:
			(end, cnt) = (end + 1, cnt + 1)
		else:
			ans.append((string[begin], cnt))
			(begin, end, cnt) = (end, end + 1, 1)
	return ans
(n, a, r, m) = map(int, input().split())
h = list(map(int, input().split()))
h = sorted(h, reverse=True)
sum_h = sum(h)
ans = 0
ceil = -(-sum_h // n)
tmp = 0
for i in range(n):
	diff = max(h[i] - ceil, 0)
	tmp += diff * m
yojoh = sum_h - sum_h // n * n
cost = (n - yojoh) * a
ans = tmp + cost
floor = sum_h // n
tmp = 0
for i in range(n):
	diff = max(floor - h[i], 0)
	tmp += diff * m
yojoh = sum_h - sum_h // n * n
cost = yojoh * r
ans = min(tmp + cost, ans)
ans2 = 10 ** 30
ptn = compress(h)
add = [0] * len(ptn)
add_cnt = [0] * len(ptn)
red = [0] * len(ptn)
red_cnt = [0] * len(ptn)
cnt = 0
move_cnt = 0
height = 0
cost = 0
for i in range(len(ptn)):
	(tmp_h, tmp_c) = ptn[i]
	cost += cnt * abs(height - tmp_h) * r
	move_cnt += cnt * abs(height - tmp_h)
	red[i] = cost
	red_cnt[i] = move_cnt
	height = tmp_h
	cnt += tmp_c
cnt = 0
height = 0
cost = 0
move_cnt = 0
ptn = ptn[::-1]
for i in range(len(ptn)):
	(tmp_h, tmp_c) = ptn[i]
	cost += cnt * abs(height - tmp_h) * a
	move_cnt += cnt * abs(height - tmp_h)
	add[i] = cost
	add_cnt[i] = move_cnt
	height = tmp_h
	cnt += tmp_c
add = add[::-1]
add_cnt = add_cnt[::-1]
for i in range(len(ptn)):
	ans2 = min(ans2, add[i] + red[i])
	min_ = min(add_cnt[i], red_cnt[i])
	cost = -min_ * (a + r) + min_ * m
	ans2 = min(ans2, add[i] + red[i] + cost)
print(min(ans, ans2))


def check(a, r, m, hhh, w):
	put = 0
	rem = 0
	for h in hhh:
		if w == h:
			continue
		if w > h:
			put += w - h
		else:
			rem += h - w
	ans = put * a + rem * r
	if put - rem >= 0:
		ans = min(ans, rem * m + (put - rem) * a)
	else:
		ans = min(ans, put * m + (rem - put) * r)
	return ans
(n, aa, rr, mm) = map(int, input().split())
hhh = list(map(int, input().split()))
l = min(hhh)
r = max(hhh)
for _ in range(50):
	m1 = (l * 2 + r) // 3
	m2 = (l + r * 2) // 3
	c1 = check(aa, rr, mm, hhh, m1)
	c2 = check(aa, rr, mm, hhh, m2)
	if c1 < c2:
		r = m2
	else:
		l = m1
print(min((check(aa, rr, mm, hhh, w) for w in range(l, r + 1))))


(n, a, r, m) = [int(s) for s in input().split()]
h = sorted([int(s) for s in input().split()])
(add, rem) = (0, sum(h) - min(h) * n)
(ans, cur) = (rem * r, rem * r)
for i in range(1, n):
	(dadd, drem) = (i, -(n - i))
	(dcost, dh) = (dadd * min(m, a + r) + (drem - dadd) * r, h[i] - h[i - 1])
	if add <= rem and add + dadd * dh > rem + drem * dh:
		rdh = (rem - add) // (dadd - drem)
		ans = min(ans, cur + rdh * dcost)
	(cur, add, rem) = (cur + dcost * dh, add + dadd * dh, rem + drem * dh)
	if add <= rem:
		ans = min(ans, cur)
cur = add * a
ans = min(ans, cur)
for i in range(n - 1, 0, -1):
	(dadd, drem) = (-i, n - i)
	(dcost, dh) = (drem * min(m, a + r) + (dadd - drem) * a, h[i] - h[i - 1])
	if add >= rem and add + dadd * dh < rem + drem * dh:
		rdh = (add - rem) // (drem - dadd)
		ans = min(ans, cur + rdh * dcost)
	(cur, add, rem) = (cur + dcost * dh, add + dadd * dh, rem + drem * dh)
	if add >= rem:
		ans = min(ans, cur)
print(ans)


import math as m

def binary_search_int(f, start, stop):
	assert start < stop
	(left, right) = (start, stop)
	while left < right:
		mid = (left + right) // 2
		if f(mid):
			left = mid + 1
		else:
			right = mid
	return right

def binary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
	assert left <= right
	while not m.isclose(left, right, rel_tol=rel_tol, abs_tol=abs_tol):
		mid = (left + right) / 2
		if f(mid):
			left = mid
		else:
			right = mid
	return right

def ternary_search_int(f, start, stop):
	assert start < stop
	invphi2 = (3 - m.sqrt(5)) / 2
	(a, d) = (start, stop - 1)
	b = a + round(invphi2 * (d - a))
	c = b + m.ceil(invphi2 * (d - b))
	fb = f(b)
	fc = f(c)
	while True:
		if fb < fc:
			if c == d:
				return d
			a = b + 1
			(b, fb) = (c, fc)
			c = b + m.ceil(invphi2 * (d - b))
			fc = f(c)
		else:
			if a == b:
				return a
			d = c - 1
			(c, fc) = (b, fb)
			b = c - m.ceil(invphi2 * (c - a))
			fb = f(b)

def ternary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
	assert left <= right
	invphi2 = (3 - m.sqrt(5)) / 2
	(a, d) = (left, right)
	b = a + invphi2 * (d - a)
	c = b + invphi2 * (d - b)
	fb = f(b)
	fc = f(c)
	while not m.isclose(a, d, rel_tol=rel_tol, abs_tol=abs_tol):
		if fb < fc:
			a = b
			(b, fb) = (c, fc)
			c = b + invphi2 * (d - b)
			fc = f(c)
		else:
			d = c
			(c, fc) = (b, fb)
			b = c - invphi2 * (c - a)
			fb = f(b)
	return c
if False:
	import doctest
	doctest.testmod()
(N, A, R, M) = map(int, input().split())
h = list(map(int, input().split()))

def cost(final_h):
	cost = 0
	over = 0
	under = 0
	for orig_h in h:
		if orig_h < final_h:
			under += final_h - orig_h
		elif orig_h > final_h:
			over += orig_h - final_h
	if M < A + R:
		move = min(over, under)
		cost += M * move
		over -= move
		under -= move
	cost += over * R + under * A
	return -cost
x = ternary_search_int(cost, 0, int(1000000000.0) + 1)
print(-cost(x))


import os
import sys
if os.path.exists('/mnt/c/Users/Square/square/codeforces'):
	f = iter(open('E.txt').readlines())

	def input():
		return next(f)
else:
	input = lambda : sys.stdin.readline().strip()
fprint = lambda *args: print(*args, flush=True)
(N, A, R, M) = map(int, input().split())
H = list(map(int, input().split()))
H = sorted(H)
M = min(M, A + R)

def calc(height):
	for cur in range(len(H)):
		if H[cur] >= height:
			break
	if H[cur] < height:
		cur += 1
	(up, down) = (0, 0)
	for h in H[:cur]:
		down += height - h
	for h in H[cur:]:
		up += h - height
	if up >= down:
		return down * M + (up - down) * R
	else:
		return up * M + (down - up) * A
(l, r) = (0, max(H) + 1)
while l + 1 < r:
	cur = (l + r) // 2
	if calc(cur) < calc(cur + 1):
		r = cur
	else:
		l = cur
print(min(calc(l), calc(r)))


(n, a, ra, m) = map(int, input().split())
h = list(map(int, input().split()))
if a + ra < m:
	(l, r) = (0, 10 ** 9 + 1)
	for _ in range(50):
		c1 = (l * 2 + r) // 3
		c2 = (l + r * 2) // 3
		p1 = 0
		p2 = 0
		q1 = 0
		q2 = 0
		for x in h:
			if c1 <= x:
				q1 += x - c1
			else:
				p1 += c1 - x
			if c2 <= x:
				q2 += x - c2
			else:
				p2 += c2 - x
		f1 = p1 * a + q1 * ra
		f2 = p2 * a + q2 * ra
		if f1 > f2:
			l = c1
		else:
			r = c2
	c1 = l + 1
	p1 = 0
	q1 = 0
	for x in h:
		if c1 <= x:
			q1 += x - c1
		else:
			p1 += c1 - x
	f1 = p1 * a + q1 * ra
	print(f1)
else:
	(l, r) = (0, 10 ** 9 + 1)
	for _ in range(55):
		c1 = (l * 2 + r) // 3
		c2 = (l + r * 2) // 3
		p1 = 0
		p2 = 0
		q1 = 0
		q2 = 0
		for x in h:
			if c1 <= x:
				q1 += x - c1
			else:
				p1 += c1 - x
			if c2 <= x:
				q2 += x - c2
			else:
				p2 += c2 - x
		if p1 > q1:
			f1 = q1 * m + (p1 - q1) * a
		else:
			f1 = p1 * m + (q1 - p1) * ra
		if p2 > q2:
			f2 = q2 * m + (p2 - q2) * a
		else:
			f2 = p2 * m + (q2 - p2) * ra
		if f1 > f2:
			l = c1
		else:
			r = c2
	c1 = l + 1
	p1 = 0
	q1 = 0
	for x in h:
		if c1 <= x:
			q1 += x - c1
		else:
			p1 += c1 - x
	if p1 > q1:
		f1 = q1 * m + (p1 - q1) * a
	else:
		f1 = p1 * m + (q1 - p1) * ra
	print(f1)


import bisect
(N, A, R, M) = map(int, input().split())
aa = sorted(map(int, input().split()))
raa = [0]
for a in aa:
	raa.append(raa[-1] + a)
ans = 10 ** 15

def calc(a):
	i = bisect.bisect_right(aa, a)
	add_n = a * i - raa[i]
	rem_n = raa[-1] - raa[i] - a * (N - i)
	if rem_n < add_n:
		tmp1 = rem_n * M + (add_n - rem_n) * A
	else:
		tmp1 = add_n * M + (rem_n - add_n) * R
	tmp2 = rem_n * R + add_n * A
	return min(tmp1, tmp2)
ans = min([calc(a) for a in set(aa)])
tmp = sum(aa) // N
ans = min([ans, calc(tmp), calc(tmp + 1)])
print(ans)


from sys import stdin

def getval(p, seq, costs):
	higher = 0
	lower = 0
	for num in seq:
		if num > p:
			higher += num - p
		elif num < p:
			lower += p - num
	ret = min(higher, lower) * costs[2]
	if higher > lower:
		ret += (higher - lower) * costs[1]
	elif higher < lower:
		ret += (lower - higher) * costs[0]
	return ret

def solve(tc):
	(n, a, r, m) = map(int, stdin.readline().strip().split())
	seq = list(map(int, stdin.readline().split()))
	if m > a + r:
		m = a + r
	costs = [a, r, m]
	lo = int(1000000000.0)
	hi = 0
	for num in seq:
		lo = min(lo, num)
		hi = max(hi, num)
	while hi - lo > 3:
		lp = lo + (hi - lo) // 3
		hp = lo + (hi - lo) // 3 * 2
		lpScore = getval(lp, seq, costs)
		hpScore = getval(hp, seq, costs)
		if lpScore < hpScore:
			hi = hp
		else:
			lo = lp
	ans = getval(lo, seq, costs)
	for i in range(lo + 1, hi + 1):
		ans = min(ans, getval(i, seq, costs))
	print(ans)
	return
tcs = 1
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n
avl = AvlTree()

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, a, b, c) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
su = sum(l)
tot = 999999999999999999
s = 0
for i in range(n):
	defi = i * l[i] - s
	exes = su - s - l[i] - (n - 1 - i) * l[i]
	ans = min(defi, exes) * min(a + b, c)
	ans += (defi - min(defi, exes)) * a + (exes - min(defi, exes)) * b
	tot = min(ans, tot)
	s += l[i]
defi = n - su % n
exes = su % n
avg1 = (su + defi) // n
avg2 = (su - exes) // n
ans1 = defi * a
ans2 = exes * b
for i in range(n):
	ans1 += max(0, l[i] - avg1) * min(a + b, c)
	ans2 += max(0, avg2 - l[i]) * min(a + b, c)
print(min(tot, ans1, ans2))


from itertools import accumulate
(n, a, r, m) = map(int, input().split())
m = min(a + r, m)
ls = list(map(int, input().split()))
ls.sort()
acc = [0] + list(accumulate(ls))
ansls = []
sm = acc[-1]
less = sm // n
more = less + 1
flg = 0
for i in range(n + 1):
	if i == 0:
		minus = 0
		plus = acc[n]
	else:
		minus = ls[i - 1] * (i - 1) - acc[i - 1]
		plus = acc[n] - acc[i] - ls[i - 1] * (n - i)
	if plus > minus:
		ansls.append(minus * m + (plus - minus) * r)
	else:
		ansls.append(plus * m + (minus - plus) * a)
	if i > 0 and less < ls[i - 1] and (not flg):
		flg = 1
		minus = less * (i - 1) - acc[i - 1]
		plus = acc[n] - acc[i - 1] - less * (n - i + 1)
		if plus > minus:
			ansls.append(minus * m + (plus - minus) * r)
		else:
			ansls.append(plus * m + (minus - plus) * a)
	if i > 0 and more < ls[i - 1] and (flg == 1):
		flg = 2
		minus = more * (i - 1) - acc[i - 1]
		plus = acc[n] - acc[i - 1] - more * (n - i + 1)
		if plus > minus:
			ansls.append(minus * m + (plus - minus) * r)
		else:
			ansls.append(plus * m + (minus - plus) * a)
print(min(ansls))


from sys import stdin, stdout
from bisect import bisect_left
import math

def main():
	(n, a, R, m) = list(map(int, stdin.readline().split()))
	arr = list(map(int, stdin.readline().split()))
	arr.sort()
	total = 0
	accu = [0] * (n + 1)
	for (i, x) in enumerate(arr):
		total += x
		accu[i] = total
	l = -1
	r = -1
	lowest = 1e+20
	for (i, x) in enumerate(arr):
		if l == -1:
			l = i
		if i + 1 == len(arr) or arr[i + 1] != arr[i]:
			r = i
		if l == -1 or r == -1:
			continue
		add = 0
		if l > 0:
			add = l * x - accu[l - 1]
		remove = 0
		if r + 1 < len(arr):
			remove = accu[n - 1] - accu[r] - (n - r - 1) * x
		move = min(remove, add)
		res = min((remove - move) * R + (add - move) * a + m * move, remove * R + add * a)
		lowest = min(lowest, res)
		l = -1
		r = -1
	cal = math.floor(accu[n - 1] / n)
	pos = bisect_left(arr, cal)
	if arr[pos] != cal:
		add = pos * cal - accu[pos - 1]
		remove = accu[n - 1] - accu[pos - 1] - (n - pos) * cal
		move = min(remove, add)
		res = min((remove - move) * R + (add - move) * a + m * move, remove * R + add * a)
		lowest = min(lowest, res)
	cal = math.ceil(accu[n - 1] / n)
	pos = bisect_left(arr, cal)
	if arr[pos] != cal:
		add = pos * cal - accu[pos - 1]
		remove = accu[n - 1] - accu[pos - 1] - (n - pos) * cal
		move = min(remove, add)
		res = min((remove - move) * R + (add - move) * a + m * move, remove * R + add * a)
		lowest = min(lowest, res)
	stdout.write(str(lowest))
main()


(n, a, r, m) = map(int, input().split())
if m > a + r:
	m = a + r
h = [int(i) for i in input().split()]

def checker(height):
	(above, below) = (0, 0)
	for i in h:
		if i > height:
			above += i - height
		elif i < height:
			below += height - i
	if below > above:
		return above * m + (below - above) * a
	elif below < above:
		return below * m + (above - below) * r
	return below * m
(lo, hi) = (0, 1000000000)
while lo < hi:
	mid = (lo + (hi - 1)) // 2
	mx = checker(mid)
	mx1 = checker(mid + 1)
	if mx < mx1:
		hi = mid
	else:
		lo = mid + 1
print(min(mx1, mx))


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def read():
	tc = 0
	if tc:
		input = sys.stdin.readline
	else:
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')

def func(mid):
	c1 = 0
	c2 = 0
	s = 0
	for i in range(n):
		if x[i] > mid:
			c1 += x[i] - mid
		if x[i] < mid:
			c2 += mid - x[i]
	if m < a + r1:
		s += min(c1, c2) * m
		if c1 > c2:
			s += (c1 - c2) * r1
		else:
			s += (c2 - c1) * a
	else:
		s = c1 * r1 + c2 * a
	return s

def solve():
	global a, r1, m, x, n
	(n, a, r1, m) = mi()
	x = li()
	mnx = min(x)
	mx = max(x)
	l = mnx
	r = mx
	ans = 0
	c = 0
	while l <= r:
		mid = l + (r - l) // 2
		if mid == mnx:
			if func(mid) <= func(mid + 1):
				ans = mid
				break
			else:
				l = mid + 1
		elif mid == mx:
			if func(mid) <= func(mid - 1):
				ans = mid
				break
			else:
				r = mid - 1
		else:
			x0 = func(mid)
			x1 = func(mid - 1)
			x2 = func(mid + 1)
			if x0 <= x1 and x0 <= x2:
				ans = mid
				break
			elif x1 < x2:
				r = mid - 1
			else:
				l = mid + 1
	print(func(ans))
solve()


(n, a, r, m) = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
prev = 0
aft = sum(h)
mincost = -1
op1 = aft // n
ne1 = 0
tm1 = 0
op2 = op1 + 1
ne2 = 0
tm2 = 0
for i in range(n):
	goal = h[i]
	if goal < op1:
		ne1 += op1
		ne1 -= goal
	else:
		tm1 += goal
		tm1 -= op1
	if goal < op2:
		ne2 += op2
		ne2 -= goal
	else:
		tm2 += goal
		tm2 -= op2
	ne = i * goal - prev
	tm = aft - (n - i) * goal
	mx = min(ne, tm)
	cost = 0
	if m < a + r:
		ne -= mx
		tm -= mx
		cost += mx * m
	cost += ne * a
	cost += tm * r
	if mincost == -1:
		mincost = cost
	mincost = min(mincost, cost)
	prev += goal
	aft -= goal
cost1 = ne1 * m + (tm1 - ne1) * r
cost2 = tm2 * m + (ne2 - tm2) * a
mincost = min(cost1, mincost)
mincost = min(cost2, mincost)
print(mincost)


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
mod = int(1000000000.0) + 7

def cal(x):
	(r1, a1) = (0, 0)
	for i in range(n):
		if h[i] >= x:
			r1 += h[i] - x
		else:
			a1 += x - h[i]
	ans = 0
	if m < r + a:
		t = min(r1, a1)
		ans += t * m
		r1 -= t
		a1 -= t
	ans += a1 * a + r1 * r
	return ans
(n, a, r, m) = mdata()
h = mdata()
s = -1
e = 10 ** 9
while 1 + s < e:
	mid = (s + e) // 2
	if cal(mid + 1) < cal(mid):
		s = mid
	else:
		e = mid
out(cal(e))


import sys
from bisect import bisect_left
input = sys.stdin.readline
(n, a, r, m) = map(int, input().split())
m = min(m, a + r)
h = list(map(int, input().split()))
h.sort()
ch = [0] + [h[i] for i in range(n)]
for i in range(1, n + 1):
	ch[i] += ch[i - 1]
sh = sum(h)
bh = h + [sh // n - 1, sh // n, sh // n + 1]
ans = 10 ** 18
for b in bh:
	i = bisect_left(h, b)
	low_need = i * b - ch[i]
	high_need = ch[-1] - ch[i] - b * (n - i)
	cost = 0
	if low_need <= high_need:
		cost += low_need * m + (high_need - low_need) * r
	else:
		cost += high_need * m + (low_need - high_need) * a
	ans = min(ans, cost)
print(ans)


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')
import bisect

def solve(arr, a, r, m, n):
	m = min(m, a + r)
	arr = sorted(arr)
	pre_fix = [0] * (n + 1)
	for (i, val) in enumerate(arr):
		pre_fix[i + 1] = pre_fix[i] + val

	def get(h):
		idx = bisect.bisect_right(arr, h)
		P = h * idx - pre_fix[idx]
		Q = pre_fix[n] - pre_fix[idx] - (n - idx) * h
		res = min(P, Q)
		P -= res
		Q -= res
		res *= m
		res += P * a
		res += Q * r
		return res
	(h1, h2) = (pre_fix[-1] // n, pre_fix[-1] // n + 1)
	res = min(get(h1), get(h2))
	for val in arr:
		res = min(res, get(val))
	return res
(n, a, r, m) = [int(j) for j in input().split()]
arr = [int(j) for j in input().split()]
print(solve(arr, a, r, m, n))


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

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

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
(n, a, r, m) = li()
l = sorted(li())
s = set(l)
cnt = [0]
for i in l:
	cnt.append(cnt[-1] + i)

def give(s):
	less = high = 0
	for i in l:
		if i < s:
			less += s - i
		elif i > s:
			high += i - s
	return [less, high]

def cost1(s, b):
	temp = 0
	return temp * m + (b - temp) * r + (s - temp) * a

def cost2(s, b):
	temp = min(b, s)
	return temp * m + (b - temp) * r + (s - temp) * a

def f2():
	ans = float('inf')
	left = 0
	right = max(l)
	while left <= right:
		mid = left + right >> 1
		(s1, b1) = give(mid)
		(s2, b2) = give(mid + 1)
		if cost2(s1, b1) < cost2(s2, b2):
			ans = min(ans, cost2(s1, b1))
			right = mid - 1
		else:
			ans = min(ans, cost2(s2, b2))
			left = mid + 1
	return ans

def f1():
	ans = float('inf')
	left = 0
	right = max(l)
	while left <= right:
		mid = left + right >> 1
		(s1, b1) = give(mid)
		(s2, b2) = give(mid + 1)
		if cost1(s1, b1) < cost1(s2, b2):
			ans = min(ans, cost1(s1, b1))
			right = mid - 1
		else:
			ans = min(ans, cost1(s2, b2))
			left = mid + 1
	return ans
print(min(f1(), f2()))


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 math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, ap, rm, mv) = RL()
	arr = RLL()
	arr.sort()

	def c(num):
		cos = 0
		(les, gre) = (0, 0)
		for i in arr:
			if i < num:
				les += num - i
			else:
				gre += i - num
		mi = min(les, gre)
		if mi * mv > mi * (rm + ap):
			cos += rm * gre + les * ap
		else:
			dif = abs(les - gre)
			cos += mi * mv + dif * (rm if gre > les else ap)
		return cos
	(l, r) = (arr[0], arr[-1])
	while l < r:
		m = (l + r) // 2
		if c(m) > c(m + 1):
			l = m + 1
		else:
			r = m
	print(c(l))
main()


def find(h, x):
	l = 0
	r = len(h) - 1
	while abs(r - l) > 1:
		c = (l + r) // 2
		if h[c] > x:
			r = c
		elif h[c] < x:
			l = c
		elif h[c] == x:
			return c
	return l + 1

def function(height):
	global h
	if h.count(height) == 0:
		less = find(h, height)
		more = len(h) - less
		less_bricks = height * less - sum(h[0:less])
		more_bricks = (height * more - sum(h[-1:-len(h) + less - 1:-1])) * -1
	else:
		less = h.index(height)
		more = len(h) - less - h.count(height)
		less_bricks = height * less - sum(h[0:less])
		more_bricks = (height * more - sum(h[-1:-len(h) + less + h.count(height) - 1:-1])) * -1
	if more_bricks >= less_bricks:
		cost = less_bricks * M + abs(more_bricks - less_bricks) * R
	else:
		cost = more_bricks * M + abs(more_bricks - less_bricks) * A
	return cost
otv = []
probably = []
(N, A, R, M) = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
height = h[0]
if A + R < M:
	M = A + R
left = h[0]
right = h[-1]
c = (left + right) // 2
flag = 0
if function(left) < function(left + 1):
	print(f'{function(left)}')
	flag = 1
elif function(right) < function(right - 1):
	print(f'{function(right)}')
	flag = 1
else:
	while flag == 0 and abs(left - right) > 2:
		if function(c - 1) < function(c):
			right = c
		elif function(c + 1) < function(c):
			left = c
		elif function(c) < function(c - 1) and function(c) < function(c + 1):
			break
		elif function(c - 1) == function(c):
			break
		c = (left + right) // 2
	print(function(c))


import sys
input = sys.stdin.readline
from bisect import *
(N, A, R, M) = map(int, input().split())
M = min(M, A + R)
h = list(map(int, input().split()))
h.sort()
acc = [0] * (N + 1)
for i in range(N):
	acc[i + 1] = acc[i] + h[i]
S = sum(h)
bs = h + [S // N - 1, S // N, S // N + 1]
ans = 10 ** 18
for b in bs:
	i = bisect_left(h, b)
	P = i * b - acc[i]
	Q = acc[N] - acc[i] - (N - i) * b
	if P >= Q:
		ans = min(ans, M * Q + (P - Q) * A)
	else:
		ans = min(ans, M * P + (Q - P) * R)
print(ans)


from sys import stdin
(n, a, r, m) = map(int, stdin.readline().split())
he = list(map(int, stdin.readline().split()))
st = min(he)
en = max(he)
ans = 10 ** 20
while st <= en:
	mid1 = st + (en - st) // 3
	mid2 = en - (en - st) // 3
	re = ad = 0
	for i in he:
		re += max(0, i - mid1)
		ad += max(0, mid1 - i)
	if m < a + r:
		cost = min(re, ad) * m
		if re < ad:
			cost += (ad - re) * a
		else:
			cost += (re - ad) * r
	else:
		cost = re * r + ad * a
	re = ad = 0
	for i in he:
		re += max(0, i - mid2)
		ad += max(0, mid2 - i)
	if m < a + r:
		cost1 = min(re, ad) * m
		if re < ad:
			cost1 += (ad - re) * a
		else:
			cost1 += (re - ad) * r
	else:
		cost1 = re * r + ad * a
	if cost > cost1:
		st = mid1 + 1
	elif cost < cost1:
		en = mid2 - 1
	else:
		st = mid1 + 1
		en = mid2 - 1
	ans = min(ans, cost1, cost)
print(ans)


import os
from sys import stdin, argv

def getval(p, seq, costs):
	higher = 0
	lower = 0
	for num in seq:
		if num > p:
			higher += num - p
		elif num < p:
			lower += p - num
	ret = min(higher, lower) * costs[2]
	if higher > lower:
		ret += (higher - lower) * costs[1]
	elif higher < lower:
		ret += (lower - higher) * costs[0]
	return ret

def solve(tc):
	(n, a, r, m) = map(int, stdin.readline().strip().split())
	seq = list(map(int, stdin.readline().split()))
	if m > a + r:
		m = a + r
	costs = [a, r, m]
	lo = int(1000000000.0)
	hi = 0
	for num in seq:
		lo = min(lo, num)
		hi = max(hi, num)
	while hi - lo > 3:
		lp = lo + (hi - lo) // 3
		hp = lo + (hi - lo) // 3 * 2
		lpScore = getval(lp, seq, costs)
		hpScore = getval(hp, seq, costs)
		if lpScore < hpScore:
			hi = hp
		else:
			lo = lp
	ans = getval(lo, seq, costs)
	for i in range(lo + 1, hi + 1):
		ans = min(ans, getval(i, seq, costs))
	print(ans)
	return
tcs = 1
ONLINE_JUDGE = 'LOCAL_TEST' not in os.environ
if not ONLINE_JUDGE:
	infile = __file__.split('.')[0] + '-test.in'
	stdin = open(infile, 'r')
	tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


def find_cost(a, r, m, heights, x):
	(inc, dec) = [0, 0]
	for h in heights:
		if h >= x:
			dec += h - x
		else:
			inc += x - h
	if inc * dec == 0 or a + r <= m:
		return a * inc + r * dec
	if inc >= dec:
		return m * dec + (inc - dec) * a
	else:
		return m * inc + (dec - inc) * r

def main():
	(n, a, r, m) = [int(x) for x in input().split()]
	heights = [int(x) for x in input().split()]
	ans = int(1e+18)
	right = int(1000000000.0) + 1
	left = 0
	while right - left > 2:
		m1 = left + (right - left) // 3
		m2 = right - (right - left) // 3
		cost_m1 = find_cost(a, r, m, heights, m1)
		cost_m2 = find_cost(a, r, m, heights, m2)
		if cost_m1 <= cost_m2:
			right = m2
		else:
			left = m1
		ans = min(cost_m1, cost_m2)
	print(ans)
main()


from bisect import bisect_left, bisect_right

class Result:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class BinarySearch:

	def __init__(self):
		pass

	@staticmethod
	def greater_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_right(func, num)
			if index == len(func):
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(omega) <= num:
				return Result(None, None)
			while alpha < omega:
				if func(alpha) > num:
					return Result(alpha, func(alpha))
				if omega == alpha + 1:
					return Result(omega, func(omega))
				mid = (alpha + omega) // 2
				if func(mid) > num:
					omega = mid
				else:
					alpha = mid

	@staticmethod
	def less_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_left(func, num) - 1
			if index == -1:
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(alpha) >= num:
				return Result(None, None)
			while alpha < omega:
				if func(omega) < num:
					return Result(omega, func(omega))
				if omega == alpha + 1:
					return Result(alpha, func(alpha))
				mid = (alpha + omega) // 2
				if func(mid) < num:
					alpha = mid
				else:
					omega = mid
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 math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

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

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
bs = BinarySearch()
for _ in range(int(input()) if not True else 1):
	(n, add, rem, move) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	move = min(move, rem + add)
	pre = [0]
	for i in range(n):
		pre += [pre[-1] + a[i]]

	def query(i, j):
		return pre[j + 1] - pre[i]

	def f(x):
		ind = bs.less_than(x + 1, a).index
		if ind is None:
			ind = -1
		required = x * (ind + 1) - query(0, ind)
		extra = query(ind + 1, n - 1) - x * (n - (ind + 1))
		if required == extra:
			return move * required
		elif required < extra:
			return move * required + (extra - required) * rem
		else:
			return move * extra + (required - extra) * add
	(alpha, omega) = (a[0], a[-1])
	while True:
		(al, om) = (alpha, omega)
		m1 = alpha + (omega - alpha) // 3
		m2 = omega - (omega - alpha) // 3
		(x, y) = (f(m1), f(m2))
		if x > y:
			alpha = m1
		else:
			omega = m2
		if (al, om) == (alpha, omega):
			break
	ans = 10 ** 69
	for i in range(alpha, omega + 1):
		ans = min(ans, f(i))
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

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

def oint():
	return int(input())
(n, a, r, m) = rint()
h = list(rint())
m = min(m, a + r)
h.sort()
psum = [0] * n
psum[0] = h[0]
for i in range(1, n):
	psum[i] += h[i] + psum[i - 1]
ans = 10 ** 99
for i in range(n):
	b1 = (i + 1) * h[i] - psum[i]
	b2 = psum[n - 1] - psum[i] - (n - 1 - i) * h[i]
	cost = 0
	if b1 > b2:
		cost += b2 * m + (b1 - b2) * a
	else:
		cost += b1 * m + (b2 - b1) * r
	ans = min(ans, cost)
havr = sum(h) // n
hr = sum(h) % n
if hr:
	havr += 1
b1 = 0
b2 = 0
cost = 0
for i in range(n):
	if h[i] < havr:
		b1 += havr - h[i]
	else:
		b2 += h[i] - havr
if b1 > b2:
	cost += b2 * m + (b1 - b2) * a
else:
	cost += b1 * m + (b2 - b1) * r
ans = min(ans, cost)
havr -= 1
b1 = 0
b2 = 0
cost = 0
for i in range(n):
	if h[i] < havr:
		b1 += havr - h[i]
	else:
		b2 += h[i] - havr
if b1 > b2:
	cost += b2 * m + (b1 - b2) * a
else:
	cost += b1 * m + (b2 - b1) * r
ans = min(ans, cost)
print(ans)


def rn():
	a = int(input())
	return a

def rl():
	a = list(map(int, input().split()))
	return a

def val(v, h, a, r, m):
	ls = 0
	ms = 0
	for i in h:
		if i < v:
			ls += v - i
		else:
			ms += i - v
	cost = min(ls, ms) * m
	if ls > ms:
		cost += (ls - ms) * a
	else:
		cost += (ms - ls) * r
	return cost

def find(s, e, h, a, r, m):
	if s == e:
		return val(s, h, a, r, m)
	elif e == s + 1:
		return min(val(s, h, a, r, m), val(e, h, a, r, m))
	md = s + (e - s) // 2
	v1 = val(md - 1, h, a, r, m)
	v2 = val(md, h, a, r, m)
	v3 = val(md + 1, h, a, r, m)
	if v2 <= v3 and v2 <= v1:
		return v2
	if v1 < v2:
		return find(s, md, h, a, r, m)
	else:
		return find(md, e, h, a, r, m)
[n, a, r, m] = rl()
h = rl()
h.sort()
if a + r < m:
	m = a + r
ans = int(2e+18)
cs = [0 for i in range(n)]
s = h[0]
e = h[-1]
print(find(s, e, h, a, r, m))