Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.

Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of $2$. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:   if the current length is at least $2$, divide the base into $2$ equal halves and destroy them separately, or  burn the current base. If it contains no avenger in it, it takes $A$ amount of power, otherwise it takes his $B \cdot n_a \cdot l$ amount of power, where $n_a$ is the number of avengers and $l$ is the length of the current base. Output the minimum power needed by Thanos to destroy the avengers' base.


-----Input-----

The first line contains four integers $n$, $k$, $A$ and $B$ ($1 \leq n \leq 30$, $1 \leq k \leq 10^5$, $1 \leq A,B \leq 10^4$), where $2^n$ is the length of the base, $k$ is the number of avengers and $A$ and $B$ are the constants explained in the question.

The second line contains $k$ integers $a_{1}, a_{2}, a_{3}, \ldots, a_{k}$ ($1 \leq a_{i} \leq 2^n$), where $a_{i}$ represents the position of avenger in the base.


-----Output-----

Output one integer — the minimum power needed to destroy the avengers base.


-----Examples-----
Input
2 2 1 2
1 3

Output
6

Input
3 2 1 2
1 7

Output
8



-----Note-----

Consider the first example.

One option for Thanos is to burn the whole base $1-4$ with power $2 \cdot 2 \cdot 4 = 16$.

Otherwise he can divide the base into two parts $1-2$ and $3-4$.

For base $1-2$, he can either burn it with power $2 \cdot 1 \cdot 2 = 4$ or divide it into $2$ parts $1-1$ and $2-2$.

For base $1-1$, he can burn it with power $2 \cdot 1 \cdot 1 = 2$. For $2-2$, he can destroy it with power $1$, as there are no avengers. So, the total power for destroying $1-2$ is $2 + 1 = 3$, which is less than $4$. 

Similarly, he needs $3$ power to destroy $3-4$. The total minimum power needed is $6$.

Difficulty: interview

Starter code:

Solutions:
ii = lambda: int(input())
mi = lambda: list(map(int, input().split()))
li = lambda: list(mi())
from bisect import bisect_left as lb, bisect_right as ub

n, k, A, B = mi()
a = li()
a.sort()

def f(l, r):
    cnt = ub(a, r) - lb(a, l)
    if cnt == 0:
        return A
    if l == r:
        return B * cnt
    m = (l + r) >> 1
    return min(B * cnt * (r - l + 1), f(l, m) + f(m + 1, r))

print(f(1, 2 ** n))


from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
N, K, A, B = map(int, input().split())
k = sorted(map(int, input().split()))
base_length = 2**N

def hoge(l, r):
    avengers = bisect_left(k, r) - bisect_left(k, l)
    size = r-l
    power = A if not avengers else B*avengers*size
    if not avengers or r-l == 1:
        return power
    else:
        mid = (r+l)//2
        return min(power, hoge(l, mid)+hoge(mid, r))


print(hoge(1, base_length+1))

# -*- coding: utf-8 -*-
# @Time    : 2019/2/4 0:20
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Creative Snap.py


def main():
    n, k, a, b = list(map(int, input().split()))
    pos = list(map(int, input().split()))
    pos.sort()

    def search(interval_left, interval_right, index_left, index_right):
        if interval_left == interval_right:
            if index_left > index_right:
                # print('Interval:', interval_left, interval_right)
                # print('ANS:', a)
                return a
            else:
                # print('Interval:', interval_left, interval_right)
                # print('ANS:', b * (index_right - index_left + 1))
                return b * (index_right - index_left + 1)
        if index_left > index_right:
            return a

        interval_mid = interval_left + (interval_right - interval_left) // 2
        # print('MID:', interval_mid)
        left, right = index_left, index_right
        index_mid = left - 1
        while left <= right:
            mid = (left + right) // 2
            if pos[mid] <= interval_mid:
                index_mid = mid
                left = left + 1
            else:
                right = right - 1

        t0 = b * (index_right - index_left + 1) * (interval_right - interval_left + 1)
        t1 = search(interval_left, interval_mid, index_left, index_mid)
        t2 = search(interval_mid + 1, interval_right, index_mid + 1, index_right)
        ans = min(t0, t1 + t2)
        # print('Interval:', interval_left, interval_right)
        # print('ANS', ans)
        return min(t0, t1 + t2)

    ret = search(1, 1 << n, 0, k - 1)
    print(ret)


def __starting_point():
    main()

__starting_point()

import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,k,A,B=list(map(int,input().split()))
K=list(map(int,input().split()))

K.sort()

def points(l,r):#[l,r)
    if r==l+1:
        x=bisect.bisect_left(K,r)-bisect.bisect_left(K,l)
        if x!=0:
            return B*x
        else:
            return A

    mid=(l+r)//2

    x=bisect.bisect_left(K,mid)-bisect.bisect_left(K,l)
    y=bisect.bisect_left(K,r)-bisect.bisect_left(K,mid)

    #print(l,r,x,y)

    if x==0 and y==0:
        return A
    elif x!=0 and y!=0:
        return points(l,mid)+points(mid,r)
    elif y==0:
        return min(A+points(l,mid),B*(x+y)*(r-l))
    elif x==0:
        return min(A+points(mid,r),B*(x+y)*(r-l))


print(points(1,2**n+1))

    
        
    
    


import bisect

n, k, A, B = [int(x) for x in input().split()]
a_is = [int(x) - 1 for x in input().split()]

a_is.sort()

def how_many(i, j):
    count = bisect.bisect_left(a_is, j) - bisect.bisect_left(a_is, i)
    # print('i, j, count', i, j, count)
    return count


def get_cost(i, j):
    count = how_many(i, j)
    if count == 0:
        return A
    elif i + 1 == j:
        return B * count
    else:
        div = (j - i) // 2
        default = B * count * (j - i)
        left = get_cost(i, i + div)
        if left > default:
            return default

        right = get_cost(i + div, j)

        if left + right > default:
            return default
        else:
            return left + right


print(get_cost(0, 2**n))


def explosion(a, x, y, q, l, r):
    if r - l == 1:
        q1 = q
        while q1 < len(a) and a[q1] < r:
            q1 += 1
        if q1 == q:
            return x
        else:
            return (q1-q)*y
    q1 = q
    while q1 < len(a) and a[q1] < (l+r)//2:
        q1 += 1
    q2 = q1
    while q2 < len(a) and a[q2] < r:
        q2 += 1
    if q1-q == 0 and q2-q1 == 0:
        return x
    if q2-q1 != 0 and q1-q != 0:
        d1, d2, d = explosion(a, x, y, q, l, (l+r)//2), explosion(a, x, y, q1, (l+r)//2, r), (q2-q)*(r-l)*y
        if d1+d2 < d:
            return d1+d2
        else:
            return d
    if q1 != q:
        d, d1 = explosion(a, x, y, q, l, (l+r)//2), (r-l)*(q1-q)*y
        if x+d < d1:
            return x+d
        else:
            return d1
    else:
        d, d1 = explosion(a, x, y, q1, (l+r)//2, r), (r-l)*(q2-q1)*y
        if x+d < d1:
            return x+d
        else:
            return d1


n, k, x, y = list(map(int, input().split()))
a = sorted(list([int(x)-1 for x in input().split()]))
print(explosion(a, x, y, 0, 0, 2**n))


import bisect

# Turn list(str) into list(int)
def getIntList(lst):
    assert type(lst) is list
    rep = []
    for i in lst:rep.append(int(i))
    return rep

n,k,A,B = getIntList(input().split())
pos = getIntList(input().split())


def calc(l,r,heros):
    assert type(heros) is list
    if len(heros) == 0: return A
    if r-l == 0: return B*len(heros)
    mid = bisect.bisect_right(heros,(l+r)//2) 
    tans = min(
        calc(l,(l+r)//2,heros[:mid])+calc((l+r)//2+1,r,heros[mid:]),
        B*len(heros)*(r-l+1)
    )
    return tans

pos.sort()
ans = calc(1,2**n,pos)
print(ans)

from bisect import bisect_left as lb, bisect_right as ub

n, k, A, B = map(int, input().split(' '))
a = sorted(map(int, input().split(' ')))

def heihei(l, r):
    cnt = ub(a, r) - lb(a, l)
    if cnt == 0:
        return A
    
    if l == r:
        return A if cnt == 0 else B * cnt
    
    mid = (l + r) >> 1
    lr, rr = heihei(l, mid), heihei(mid + 1, r)

    return min(B * cnt * (r - l + 1), lr + rr)


print(heihei(1, 2 ** n))

def get(tl, tr, a):
	nonlocal A, B
	if len(a) == 0:
		return A
	if tl == tr:
		return len(a) * B
	tm = (tl + tr) // 2
	c, d = [], []
	for x in a:
		if x <= tm:
			c += [x]
		else:
			d += [x]
	return min(B * len(a) * (tr - tl + 1), get(tl, tm, c) + get(tm + 1, tr, d))

n, k, A, B = map(int, input().split())
a = list(sorted(list(map(int, input().split()))))
print(get(1, 1 << n, a))

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

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

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


n, k, A, B=mi()

avg=lm()

#adic=[dd(int) for i in range(n)]



#for j in avg:
	
	
#	for i in range(n):
#		place=math.ceil(j/(2**(n-i-1)))
#		
#		adic[i][place]+=1
#
		
#print(adic)



def divide(startbin, endbin, level, currentas, currentlength):
	#print(currentas,level)
	if currentlength==0:
		return A
	

	astart=[]
	aend=[]
	midpoint=startbin*2**(n-level)
	for a in currentas:
		if a<=midpoint:
			astart.append(a)
		else:
			aend.append(a)
	
	binlength=2**(n-level)
	#dicheight=level-1
	#a1=adic[dicheight][startbin]
	#a2=adic[dicheight][endbin]
	#print(astart,aend)
	

	 #a1+a2==0:
	 #	return A
	
	a1=len(astart)
	a2=len(aend)
	
	cost1=(a1+a2)*B*(binlength*2)

	#if cost1<=A:
	#	return cost1


	if level==n:
		if a1==0:
			subcost1=A
		else:
			subcost1=B*a1
		if a2==0:
			subcost2=A
		else:
			subcost2=B*a2
		cost2=subcost1+subcost2
	else:
		cost2=divide(startbin*2-1,startbin*2, level+1,astart, a1)+divide(endbin*2-1, endbin*2,level+1,aend, a2)
		
	return min(cost1,cost2)


print(divide(1,2,1,avg, k))



def ans(arr,l,r,a,b):
    if len(arr) == 0:
        return a
    if l == r:
        return len(arr)*b
    arr_left = []
    arr_right = []
    mid = (l+r)//2
    for el in arr:
        if l <= el <= mid:
            arr_left+=[el]
        if mid+1 <= el <= r:
            arr_right+=[el]
    return min(b*len(arr)*(r-l+1),ans(arr_left, l,mid,a,b) + ans(arr_right,mid+1,r,a,b))

n,k,a,b = list(map(int,input().split()))
arr = [int(i)-1 for i in input().split()]

print(ans(arr,0,(1<<n)-1,a,b))


from bisect import bisect_left, bisect_right

n, k, a, b = [int(x) for x in input().split()]
pos = [int(x) for x in input().split()]
na = {}
v  = {}
for i in pos:
    na[i] = na.get(i, 0) + 1
    v[i]  = b * na[i]
l = 2
t = 2
while t <= n + 1:
    xna = {}
    for i in na:
        j = (i + 1) // 2
        xna[j] = xna.get(j, 0) + na[i]
    na = xna
    xv = {}
    for i in na:
        j = i * 2
        xv[i] = min(b * na[i] * l, v.get(j-1, a) + v.get(j, a))
    v = xv
    l *= 2
    t += 1
print(v[1])

n, k, A, B = list(map(int, input().split()))


def solve(l, r, a):
    # print(l, r, a)
    if (len(a) == 0): return A
    if (l == r): return B * len(a)
    mid = (l + r) // 2
    lx = []
    rx = []
    for i in a:
        if (i <= mid):
            lx.append(i)
        else:
            rx.append(i)
    return min(B * len(a) * (r - l + 1), solve(l, mid, lx) + solve(mid + 1, r, rx))


a = list(map(int, input().split()))
print(solve(1, 1 << n, a))


def inint():
    return int(input())
def mp():
    return list(map(int,input().split()))
from bisect import bisect,bisect_left
    
def sol(i,j):
    works=bisect(a,j)-bisect_left(a,i)
    if works==0:return A
    if i==j:return B*works
    m=(i+j)>>1
    return min(B*(j-i+1)*works,sol(i,m)+sol(m+1,j))    
    
n,k,A,B=mp()
a=list(mp())
a.sort()
#print(a)
print(sol(1,2**n))


(n,k,a,b)=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
def se(st,en):
	nonlocal l
	c=0
	lo=0
	hi=len(l)-1
	while lo<=hi:
		mid=(lo+hi)//2
		if l[mid]<=en:
			lo=mid+1

		else:
			hi=mid-1

	c+=hi
	lo=0
	hi=len(l)-1
	while lo<=hi:
		mid=(lo+hi)//2
		if l[mid]>=st:
			hi=mid-1

		else:
			lo=mid+1

	return c-lo+1





def f(st,en):
	#print(st,en)
	"""
	if c>20:
		return 0

	else:
		c+=1"""
	
	nonlocal n,a,b
	t=se(st,en)
	#print(st,en,t)
	if st==en:
		if t==0:
			#print("A:",a,st,en)
			return a

		else:
			#print("B:",b*t*1,st,en)
			return b*t*1

	else:
		le=(en-st+1)
		if t==0:
			#print("A:",a,st,en)
			return a

		else:
			return min(b*t*le,f(st,st+le//2-1)+f(st+le//2,en))
			#print("J",j,st,en)
			#return j


print(f(1,2**n))
#print(se(l,3,4))


def get(tl, tr, a):
	nonlocal A, B
	if len(a) == 0:
		return A
	if tl == tr:
		return len(a) * B
	tm = (tl + tr) // 2
	c, d = [], []
	for x in a:
		if x <= tm:
			c += [x]
		else:
			d += [x]
	return min(B * len(a) * (tr - tl + 1), get(tl, tm, c) + get(tm + 1, tr, d))

n, k, A, B = map(int, input().split())
a = list(sorted(list(map(int, input().split()))))
print(get(1, 1 << n, a))

n, k, A, B = list(map(int, input().split()))
n = 2 ** n
a = list(sorted(list(map(int, input().split()))))

def recurs(start, end, array):
	if len(array) == 0: 
		return A
	if end - start == 1:
		return B*len(array)

	middle = (start + end)//2
	c, d = [], []
	for x in array:
		if x < middle:
			c += [x]
		else:
			d += [x] 
	return  min(B*len(array)*(end - start), recurs(start, middle, c) + recurs(middle, end, d))

print(recurs(1, n + 1, a))

# import numpy as np

# print('Введите количество уравнений:')
# n = int(input())
# print('Введите линейные коэфициенты:')
# a = np.array([list(float(t) for t in input().split()) for i in range(n)])

# print(a.shape)


n, k, A, B = list(map(int, input().split()))
n = 2 ** n
a = sorted(list(map(int, input().split())))

def recurs(start, end, sum_all, array):
	if sum_all == 0: 
		return A
	else:
		energy = B*(end - start)*sum_all

	if end - start == 1:
		return energy
	c, d = [], []
	for x in array:
		if x < ((start + end)//2):
			c += [x]
		else:
			d += [x]
	first = len(c)
	second = sum_all - first
	tmp = recurs(start, (start + end)//2, first, c) 
	tmp += recurs((start + end)//2, end, second, d)
	return  (energy < tmp) * energy + (1 - (energy < tmp))*tmp

print(recurs(1, n + 1, k, a))

# import numpy as np

# print('Введите количество уравнений:')
# n = int(input())
# print('Введите линейные коэфициенты:')
# a = np.array([list(float(t) for t in input().split()) for i in range(n)])

# print(a.shape)


from collections import Counter
from functools import reduce

n, k, A, B = list(map(int, input().split()))

positions = sorted(list([int(s)-1 for s in input().split()]))

d_h_counts = Counter(positions)
h_indices = d_h_counts

for ind in h_indices:
    h_indices[ind] = (B * h_indices[ind], h_indices[ind])


ind_filled = sorted(h_indices)

def reduce(ind_filled, d_values, ll):
    """
    Merge adjacent non-empty blocks and compute the indices of the new non-empty blocks
    :param d_values:
    :return:
    """

    index = 0
    d_res = {}
    out_ind = []
    while index < len(ind_filled):

        ai = ind_filled[index]

        if index == len(ind_filled)-1 or ind_filled[index] // 2 != ind_filled[index+1] // 2:
            d_res[ai//2] = (min(A + d_values[ai][0], d_values[ai][1] * B * 2 * ll), d_values[ai][1])
            out_ind.append(ai//2)
            index += 1


        elif ind_filled[index] // 2 == ind_filled[index+1] // 2:
            # merge
            anext = ind_filled[index+1]
            d_res[ai//2] = (min(d_values[ai][0] + d_values[anext][0],
                                   (d_values[ai][1] + d_values[anext][1]) * B * 2 * ll),
                               d_values[ai][1] + d_values[anext][1])
            out_ind.append(ai//2)

            index += 2

    return out_ind, d_res

ll = 1

arr_ind = ind_filled

npow = 0

while npow < n:

    arr_ind, d_h_counts = reduce(arr_ind, d_h_counts, ll)

    ll *= 2
    npow += 1


k = list(d_h_counts.keys())[0]
print(d_h_counts[k][0])