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: interview

Starter code:

Solutions:
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(1e9)
mn = int(1e18)

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)

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(1e20)
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
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
    '''
    print('n: %d, a, %d, r: %d, m: %d' % (n, a, r, m))
    print('more_val: %d, less_val: %d, move_val: %d' % (more_val, less_val, move_val))
    print('val1: %d' % (val1))
    print('val2: %d' % (val2))
    print('target: %d, val: %d' % (target, min(val1, val2)))
    '''
    return min(val1, val2)

def main():
    n, a, r, m = list(map(int, input().split()))
    A = list(map(int, input().split()))
    left = min(A)
    right = max(A)
    while right - left > 2:
        #print('left: %d, right: %d' % (left, right))
        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))

def __starting_point():
    main()

__starting_point()

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]
        # print(x, lidx, ridx, much, less)
        res = min(m, a+r) * min(much, less)
        if much > less:
            res += r * (much - less)
        else:
            res += a * (less - much)
        return res

    # print([cost(i) for i in range(10)])
    lo, hi = min(hl) - 1, max(hl) + 1
    while hi - lo > 3:
        mlo = (hi + lo*2)//3
        mhi = (hi*2 + lo)//3
        # print(mlo, cost(mlo))
        if cost(mlo) < cost(mhi):
            hi = mhi
        else:
            lo = mlo
    print(min(cost(i) for i in range(lo, hi+1)))
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()


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 #Higher than next
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))


n, a, ra, m = list(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 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

def __starting_point():
    solve()
__starting_point()

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

    #print(MINUS,PLUS,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(ave,indmin,indmax,MINUS,PLUS,ANS)
    

print(ANS)






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

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
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 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
    # print(height, cur, N, H[cur], H)
    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

# print(calc(8))

# print(Hs)
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(l, r)
# print(calc(l), calc(r))
print(min(calc(l), calc(r)))


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
    #0~q弾で考え
    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

    #q+1~max(h)
    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 bisect
N, A, R, M = list(map(int, input().split()))

aa = sorted(map(int, input().split()))

raa = [0]
for a in aa:
    raa.append(raa[-1] + a)

ans = 10 ** 15


# a に揃える時のコスト
def calc(a):
    i = bisect.bisect_right(aa, a)
    add_n = a * i - raa[i]
    rem_n = (raa[-1] - raa[i]) - (a * (N - i))

    # move する
    if rem_n < add_n:
        tmp1 = rem_n * M + (add_n - rem_n) * A
    else:
        tmp1 = add_n * M + (rem_n - add_n) * R

    # move しない
    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)