After finding and moving to the new planet that supports human life, discussions started on which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the universal currency.

These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and accumulated a lot of them throughout the years. Unfortunately, when paying something in bitcoin everyone can see how many bitcoins you have in your public address wallet. 

This worried Alice, so she decided to split her bitcoins among multiple different addresses, so that every address has at most $x$ satoshi (1 bitcoin = $10^8$ satoshi). She can create new public address wallets for free and is willing to pay $f$ fee in satoshi per transaction to ensure acceptable speed of transfer. The fee is deducted from the address the transaction was sent from. Tell Alice how much total fee in satoshi she will need to pay to achieve her goal.


-----Input-----

First line contains number $N$ ($1 \leq N \leq 200\,000$) representing total number of public addresses Alice has.

Next line contains $N$ integer numbers $a_i$ ($1 \leq a_i \leq 10^9$) separated by a single space, representing how many satoshi Alice has in her public addresses.

Last line contains two numbers $x$, $f$ ($1 \leq f < x \leq 10^9$) representing maximum number of satoshies Alice can have in one address, as well as fee in satoshies she is willing to pay per transaction. 


-----Output-----

Output one integer number representing total fee in satoshi Alice will need to pay to achieve her goal.


-----Example-----
Input
3
13 7 6
6 2

Output
4



-----Note-----

Alice can make two transactions in a following way:

0. 13 7 6 (initial state)

1. 6 7 6 5 (create new address and transfer from first public address 5 satoshies)

2. 6 4 6 5 1 (create new address and transfer from second address 1 satoshi)

Since cost per transaction is 2 satoshies, total fee is 4.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=(list(map(int,input().split())))
a.sort(reverse=True)
x,f=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i]>x:
        r=(a[i]-x)//(x+f)
        if (a[i]-x)%(x+f):
            r+=1
        ans+=(f*r)
    else:
        break
print(ans)


I=lambda:map(int,input().split())
n=int(input())
a=(list(I()))
a.sort(reverse=True)
x,f=I()
summ=0
for i in range(n):
    if a[i]>x:
        r=(a[i]-x)//(x+f)
        if (a[i]-x)%(x+f):
            r+=1
        summ+=(f*r)
    else:
        break
print(summ)

n = int(input())
rek = list(map(int,input().split()))
mx, pay = map(int,input().split())
ans = 0
import math
for i in rek:
    if i > mx:
        ans += pay * (math.ceil((i-mx)/(mx+pay)))
print(ans)

# -*- coding: utf-8 -*-
from math import ceil

def problem(in1, in2, in3):
    n = int(in1)
    balances = list(map(int, in2.split()))
    
    limit = list(map(int, in3.split()))[0]
    fee = list(map(int, in3.split()))[1]
    
    tx_size = limit + fee
    
    tx_count = 0

    for index, balance in enumerate(balances):
        tx_needed = ceil((balance - limit) / tx_size)
        tx_count += tx_needed

    return tx_count * fee

def __starting_point():
    in1 = input()
    in2 = input()
    in3 = input();

    result = problem(in1, in2, in3)
    
    print(result)

__starting_point()

import math
n=int(input())
a=list(map(int,input().split()))
s=0
m,f=map(int,input().split())
for i in a:
    if i>m:
        s+=math.ceil((i-m)/(f+m))*f
print(s)    

n=int(input())
a=[int(x) for x in input().split()]
x,f=[int(x) for x in input().split()]
res=0
for i in a:
    if(i>x):
        res+=f*int(i/(f+x))
        if(i%(f+x)>x):
            res+=f
        # print(int(i%(f+x)))
print(res)


n,c=int(input()),0
a=list(map(int,input().split()))
x,f=map(int,input().split())
for i in a:
    if i>x:
        if (i-x)%(x+f)==0:
            c+=(i-x)//(x+f)
        else:
            c+=(i-x)//(x+f)+1
print(c*f)

import math

a = int(input())

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


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

output = 0
for i in b:
	output += (i + c[1] - 1)//(c[0] + c[1])
	
print (output * c[1])

def g(q, x, f, a):
	if(((a + q - 1) // q) - ((q - 1) * f) <= x):
		return True
	else:
		return False

s = input()
n = int(s)


s = input()
y = s.split()

s = input()
s = s.split()

x = int(s[0])
f = int(s[1])

ans = 0

for i in y:
	ans += (int(i) + f - 1) // (x + f)

print(ans * f)



#JMD
#Nagendra Jha-4096
import sys
import bisect

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans

def search(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect.bisect_right(a, x)
    if(i==0):
        return -1
    return i-1



##### Main ####
n=int(input())
a=list(map(int, sys.stdin.readline().split(' ')))
x,f=map(int, sys.stdin.readline().split(' '))

ans=0

for aa in a:
    if(aa<=x):
        continue
    val=(aa-x)//(x+f)
    if(val*(x+f)<aa-x):
        val+=1
    ans+=val
print(f*ans)
    

    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

n = int( input())
publicAd =list(map(int,input().split(' ')))
maxx, fee = list(map(int,input().split(' ')))
count =0
for temp in publicAd:
    if temp >maxx:
        t = (temp-maxx)/(maxx+fee) 
        count +=1 + (int(t) if t >1 else 0)
print(count*fee)

import math
n=int(input())
a=list(map(int,input().split()))
x,f=map(int,input().split())
t=x+f
ans=0
for i in a:
  if(i>x):
    ans+=int(math.ceil(((i-x)/t)))
print(ans*f)

num_addresses = int(input())
addresses = list(map(int, input().split()))
max_satoshies, fee = list(map(int, input().split()))
movements = 0
for address in addresses:
    to_move = address - max_satoshies
    if to_move > 0:
        movements += to_move // (max_satoshies + fee)
        if to_move % (max_satoshies + fee) != 0:
            movements += 1
print(movements * fee)


import bisect
import math
n=int(input())
vallet=[]
vallet=list(map(int,input().strip().split()))
maxst,fee=list(map(int,input().strip().split()))
vallet.sort()
index = bisect.bisect(vallet, maxst)

numsplit=0
for i in range(index,len(vallet)):
    numsplit+=math.ceil(float(vallet[i]-maxst)/(maxst+fee))

print(numsplit*fee)


n = int(input())
a = list(map(int, input().split()))
max, fee = list(map(int, input().split()))
total = 0
a.sort(reverse=True)
for i in range(n):
    if a[i]> max:
        num = -(-(a[i]-max)//(max+fee))
        total = total + fee*num
    else:
        break

print(total)


import math
n= int (input())
ch=input().split()
a=list()
for i in range(n):
    a.append(int(ch[i]))
ch=input().split()
max1=int(ch[0])
fee=int(ch[1])
a.sort(reverse=True)
result=0
for i in range(n):
    if (a[i]<=max1):
        break
    k=a[i]+fee
    result+=(math.ceil(k/(fee+max1)))-1
print (result*fee)

import math
n=int(input())
a=[int(s) for s in input().split()]
x,f=map(int,input().split())
ans=0
for i in range(n):
    if a[i]<=x:
        continue
    if a[i]//(x+f)>0:
        ans+=(a[i]//(x+f))*f
        a[i]-=a[i]//(x+f)*(x+f)
        if a[i]<=x:
            continue        
        ans+=a[i]//x*f
    else:
        ans+=a[i]//x*f
print(ans)

import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]
x, f = map(int, input().split())
k = 0
for i in range(n):
    if a[i] >= x + f:
        k += a[i]//(x + f)
        if a[i] % (x + f) > x:
            k += 1
    elif x < a[i] < x + f:
        k += 1
print(k*f)

import math
input()	
a=list(map(int,input().split()))
x,y=list(map(int,input().split()))
s=0
for i in a:
	if i>x:
		s+=math.ceil((i-x)/(x+y))
print(int(s*y))	


import math
def round_school(x):
    i, f = divmod(x, 1)
    return int(i + ((f >= 0.5) if (x > 0) else (f > 0.5)))
line1 = input()
line2 = input()
line3 = input()
addrs = list()
count = int(line1.strip())
for elem in line2.split():
    addrs.append(int(elem))
#addrs = list(map(int, line2.split()))
intline3 = list(map(int, line3.split()))
maxaddr  = intline3[0]
fees = intline3[1]
#print(str(count))
#print(str(addrs))
#print(str(maxaddr))
#print(str(fees))
idx = 0
s2 = 0
transactions = 0
val = 0.0
initiallen = len(addrs)
while(idx < initiallen):
    if(( addrs[idx] > maxaddr) and ( addrs[idx] <= (maxaddr + fees))):
        transactions = transactions + 1
        #continue
    elif( ( addrs[idx] > (maxaddr + fees)) and ( addrs[idx] <= (2*maxaddr + fees))):
        transactions = transactions + 1
        #continue
    elif( addrs[idx] > (2*maxaddr+fees)):        
        mult = int(math.floor(addrs[idx]/(maxaddr + fees)))
        transactions = transactions + mult
        val = addrs[idx] - mult * (maxaddr + fees) 
        if(val > maxaddr):
            #if( val > (maxaddr + fees)):
            if(val > (2 + fees)):
                transactions = transactions + 1                    
    idx = idx + 1               

print(transactions*fees)
    



import math
n=input()
a=list(map(int,input().split()))
x,f=list(map(int,input().split()))
ans=0
for i in a:
	if i>x:
		ans+= math.ceil((i-x)/(x+f))

print((ans)*f)


import sys
from sys import stdin,stdout
n=int(stdin.readline())
coins=list(map(int,stdin.readline().split(' ')))
coins.sort()
x,f=list(map(int,stdin.readline().split(' ')))
flag1=True
for i in range(len(coins)):
  if coins[i]>x:
    coins=coins[i:];flag1=False
    break

if flag1:
  coins=[]
ctr=0
'''
flag2=True
for i in range(len(coins)):
  if coins[i]>sc:
    coins=coins[i:]
    ctr+=(i+1)
    flag2=False
    break
if flag2:
  ctr=len(coins)
  coins=[]
'''
#print(coins)
def mainkaam(e):
  nonlocal x,f
  t1= e//(x+f)
  t2=e%(x+f)
  if t2>x:
    return t1+1
  else:
    return t1


for i in coins:
  #print(mainkaam(i),i)
  ctr+=(mainkaam(i))

print(ctr*f)




n = int(input())
coshelki = [int(i) for i in input().split()]
x, f = (int(i) for i in input().split())

sum = 0
for i in coshelki:
    perevody = i // (x + f)
    if i - perevody * (x + f) > x:
        perevody += 1
    sum += perevody

print(f * sum)

def g(q, x, f, a):
	if(((a + q - 1) // q) - ((q - 1) * f) <= x):
		return True
	else:
		return False

s = input()
n = int(s)


s = input()
y = s.split()

s = input()
s = s.split()

x = int(s[0])
f = int(s[1])

ans = 0

for i in y:
	ans += (int(i) + f - 1) // (x + f)

print(ans * f)

import math
NN = int(input())
AI = list(map(int,input().split()))
XX,FF = list(map(int,input().split()))
length = len(AI)
extra = 0
for xx in AI:
    if xx>XX:
        extra+=math.ceil((xx-XX)/(XX+FF))
print(extra*FF)