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$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Divide and conquer

Mathematics

Complete search


Solutions:
import sys
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100090)

def min_cost(l, r, pos, a, b):
	cnt = br(pos, r) - bl(pos, l)
	if cnt == 0:
		return a
	curr = b * cnt * (r - l + 1)
	if l == r:
		return curr
	m = (l + r) // 2
	return min(curr, min_cost(l, m, pos, a, b) + min_cost(m + 1, r, pos, a, b))
(n, k, a, b) = map(int, input().split())
pos = [int(x) for x in input().split()]
pos.sort()
print(min_cost(1, 2 ** n, pos, a, b))


def func(arr, l, r):
	if len(arr) == 0:
		return A
	elif l == r:
		return B * len(arr)
	else:
		z = (l + r) // 2
		back = []
		fow = []
		for i in arr:
			if i <= z:
				back.append(i)
			else:
				fow.append(i)
		return min(B * len(arr) * (r - l + 1), func(back, l, z) + func(fow, z + 1, r))
(n, k, A, B) = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
print(func(lst, 1, 2 ** n))


def helper(start, end, aveL, aveR):
	if aveR - aveL == -1:
		return A
	if start == end:
		return B * (aveR - aveL + 1)
	temp = start + (end - start) // 2
	(l, r) = (aveL, aveR)
	while l <= r:
		mid = l + (r - l) // 2
		if avengers[mid] > temp:
			r = mid - 1
		else:
			l = mid + 1
	return min(B * (aveR - aveL + 1) * (end - start + 1), helper(start, temp, aveL, l - 1) + helper(temp + 1, end, l, aveR))
(n, k, A, B) = map(int, input().split())
avengers = sorted(map(int, input().split()))
print(helper(1, 2 ** n, 0, k - 1))


import bisect
(n, k, A, B) = map(int, input().split())
X = sorted([int(a) - 1 for a in input().split()])

def calc(l, r, S):
	if len(S) == 0:
		ret = A
	elif r - l == 1:
		ret = B * len(S)
	else:
		m = (l + r) // 2
		SL = []
		SR = []
		for s in S:
			if s < m:
				SL.append(s)
			else:
				SR.append(s)
		if len(SL) == 0:
			ret = min(A + calc(m, r, SR), B * len(S) * (r - l))
		elif len(SR) == 0:
			ret = min(A + calc(l, m, SL), B * len(S) * (r - l))
		else:
			ret = calc(l, m, SL) + calc(m, r, SR)
	return ret
print(calc(0, 2 ** n, X))


import sys
import math
import collections
import bisect
import itertools
import decimal
import heapq
INF = 10 ** 20
MOD = 10 ** 9 + 7

def ni():
	return int(sys.stdin.buffer.readline())

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

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

def na1():
	return list(map(lambda x: int(x) - 1, sys.stdin.buffer.readline().split()))

def flush():
	return sys.stdout.flush()

def nicf():
	return int(sys.stdin.readline())

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

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

def na1cf():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def main():
	(n, k, a, b) = ns()
	v = na1()
	v.sort()

	def dfs(l, r, arr):
		lidx = bisect.bisect_left(arr, l)
		ridx = bisect.bisect_left(arr, r)
		vcnt = ridx - lidx
		if r - l == 1:
			return a if vcnt == 0 else b * vcnt
		if vcnt == 0:
			return a
		cost = b * vcnt * (r - l)
		m = (l + r) // 2
		lv = dfs(l, m, arr)
		rv = dfs(m, r, arr)
		return min(cost, lv + rv)
	ans = dfs(0, 1 << n, v)
	print(ans)
main()


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

def min_power(l, h, a):
	if len(a) == 0:
		return A
	elif l == h:
		return B * len(a)
	else:
		mid = (l + h) // 2
		left = []
		right = []
		for i in a:
			if i <= mid:
				left.append(i)
			else:
				right.append(i)
		pow_a = len(a) * (h - l + 1) * B
		pow_b = min_power(l, mid, left) + min_power(mid + 1, h, right)
		return min(pow_a, pow_b)
print(min_power(1, pow(2, n), avg))


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


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
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')
(n, k, a, b) = map(int, input().split())
from bisect import bisect_right as br
from bisect import bisect_left as bl
p = list(map(int, input().split()))
p.sort()

def dp(i, j, nb):
	if i == j:
		if nb == 0:
			return a
		return nb * b
	if nb == 0:
		c = a
		return c
	else:
		c = b * nb * (j - i + 1)
	r = i + (j - i) // 2
	l = r + 1
	nbl = br(p, r) - bl(p, i)
	nbr = nb - nbl
	return min(c, dp(i, r, nbl) + dp(l, j, nbr))
print(dp(1, 2 ** n, k))


import sys
from atexit import register
from bisect import bisect_left, bisect_right
from io import FileIO, StringIO
sys.stdin = StringIO(FileIO(0).read().decode())
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.stdout = StringIO()
register(lambda : FileIO(1, 'w').write(sys.stdout.getvalue().encode()))

def main():
	(n, k, A, B) = map(int, input().split())
	a = sorted(map(int, input().split()))

	def solve(lo, hi):
		(start, end) = (bisect_left(a, lo), bisect_right(a, hi))
		if lo == hi and a[end - 1] == lo:
			return B * (end - start)
		if start == end:
			return A
		mi = (lo + hi) // 2
		return min(B * (end - start) * (hi - lo + 1), solve(lo, mi) + solve(mi + 1, hi))
	print(solve(1, 2 ** n))
main()


(n, k, a, b) = map(int, input().split())
arr = sorted(map(int, input().split()))
el = None
c = 0
d = []
for e in arr:
	if el is None:
		el = e
		c = 1
	elif el == e:
		c += 1
	else:
		d.append((el - 1, c, c * b))
		el = e
		c = 1
d.append((el - 1, c, c * b))
for g in range(0, n):
	i = 0
	new_d = []
	c_l = 2 ** (g + 1)
	while i < len(d) - 1:
		(el, c, cost) = d[i]
		(el2, c2, cost2) = d[i + 1]
		if el % 2 == 0 and el2 - el == 1:
			n_c = c + c2
			new_d.append((int(el // 2), n_c, min(cost2 + cost, b * c_l * n_c)))
			i += 2
		else:
			new_d.append((int(el // 2), c, min(cost + a, b * c_l * c)))
			i += 1
	if i < len(d):
		(el, c, cost) = d[-1]
		new_d.append((int(el // 2), c, min(cost + a, b * c_l * c)))
	d = new_d
print(d[0][2])


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
(n, k, A, B) = inpl()
a = inpl_1()
a.sort()

def dfs(l, r, num=k):
	if r - l == 1:
		return A if num == 0 else B * num
	if num == 0:
		return A
	(l1, r1, l2, r2) = (l, l + (r - l) // 2, l + (r - l) // 2, r)
	num1 = bisect_left(a, r1) - bisect_left(a, l1)
	num2 = bisect_left(a, r2) - bisect_left(a, l2)
	mi = min(B * num * (r - l), dfs(l1, r1, num1) + dfs(l2, r2, num2))
	return mi
print(dfs(0, 2 ** n))


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

def min_cost(l, r, full):
	if len(full) == 0:
		return A
	elif l == r:
		return B * len(full)
	else:
		mid = (l + r) // 2
		left = []
		right = []
		for i in full:
			if i <= mid:
				left.append(i)
			else:
				right.append(i)
		return min(len(full) * (r - l + 1) * B, min_cost(l, mid, left) + min_cost(mid + 1, r, right))
print(min_cost(1, 2 ** n, f))


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


from bisect import bisect, bisect_left
(n, k, A, B) = map(int, input().split())
a = [int(i) for i in input().split()]
a = sorted(a)
l = 2 ** n

def solve(i, j):
	num_a = bisect(a, j) - bisect_left(a, i)
	if num_a == 0:
		p = A
	elif i == j:
		p = B * num_a
	else:
		m = i + j >> 1
		p = min(B * num_a * (j - i + 1), solve(i, m) + solve(m + 1, j))
	return p
print(solve(1, l))


import bisect

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)


(N, K, A, B) = map(int, input().split())
DATA = sorted(list(map(int, input().split())))
idx = 1
next_data = [(DATA[0], 1)]
while idx < len(DATA):
	if DATA[idx] == next_data[-1][0]:
		next_data[-1] = (DATA[idx], next_data[-1][1] + 1)
	else:
		next_data.append((DATA[idx], 1))
	idx += 1
DATA = next_data
DATA = [(i - 1, i - 1, n, B * n) for (i, n) in DATA]
size = 1
for _ in range(N):
	next_data = []
	size *= 2
	idx = 0
	while idx < len(DATA):
		(i, j, n, val) = DATA[idx]
		ni = i // size * size
		nj = (i // size + 1) * size - 1
		if idx < len(DATA) - 1 and DATA[idx + 1][1] == nj:
			(i2, j2, n2, val2) = DATA[idx + 1]
			next_data.append((ni, nj, n + n2, min(val + val2, B * size * (n + n2))))
			idx += 1
		else:
			next_data.append((ni, nj, n, min(val + A, B * size * n)))
		idx += 1
	DATA = next_data
print(DATA[0][3])


(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):
	nonlocal n, a, b
	t = se(st, en)
	if st == en:
		if t == 0:
			return a
		else:
			return b * t * 1
	else:
		le = en - st + 1
		if t == 0:
			return a
		else:
			return min(b * t * le, f(st, st + le // 2 - 1) + f(st + le // 2, en))
print(f(1, 2 ** n))


(p, k, A, B) = [int(e) for e in input().split()]
K = tuple([int(e) for e in input().split()])
d = {}

def thanos(p, K, A, B):
	if p == 0:
		if len(K) == 0:
			return A
		else:
			return B * len(K)
	if len(K) != 0:
		op1 = B * len(K) * 2 ** p
	else:
		op1 = A
	ref = 2 ** p // 2
	Kl = tuple([e for e in K if e <= ref])
	Kr = tuple([e - ref for e in K if e > ref])
	if (p, Kl) in d:
		LL = d[p, Kl]
	else:
		tmp = thanos(p - 1, Kl, A, B)
		d[p, Kl] = tmp
		LL = tmp
	if (p, Kr) in d:
		RR = d[p, Kr]
	else:
		tmp = thanos(p - 1, Kr, A, B)
		d[p, Kr] = tmp
		RR = tmp
	op2 = LL + RR
	return min(op1, op2)
print(thanos(p, K, A, B))


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.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('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
(n, k, a, b) = li()
l = sorted(li())

def recursive(i, j):
	temp = br(l, j) - bl(l, i)
	if not temp:
		return a
	if i == j:
		return b * temp
	mid = i + j >> 1
	return min(b * temp * (j - i + 1), recursive(i, mid) + recursive(mid + 1, j))
print(recursive(1, 2 ** n))


import collections
import time
import os
import sys
import bisect
import heapq
(N, K, A, B) = map(int, input().split())
positions = [int(x) for x in input().split()]
positions.sort()

def count(l, r):
	a = bisect.bisect_left(positions, l)
	b = bisect.bisect_right(positions, r)
	return b - a

def solve(l, r):
	(a, b) = (bisect.bisect_left(positions, l), bisect.bisect_right(positions, r))
	x = b - a
	ans = 0
	if x == 0:
		ans = A
	else:
		ans = B * x * (r - l + 1)
	if l == r or x == 0:
		return ans
	m = (l + r) // 2
	ans = min(ans, solve(l, m) + solve(m + 1, r))
	return ans
print(solve(1, 1 << 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) = map(int, input().split())
a = sorted(list(map(lambda x: int(x) - 1, input().split())))
print(explosion(a, x, y, 0, 0, 2 ** n))


from sys import stdin

def input():
	return stdin.readline()[:-1]

def recur(l, r, A, B, avengers):
	if not avengers:
		return A
	if l == r:
		return B * len(avengers)
	else:
		cost = B * len(avengers) * (r - l + 1)
		mid = (l + r) // 2
		x = []
		y = []
		for i in avengers:
			if i <= mid:
				x.append(i)
			else:
				y.append(i)
		cost = min(cost, recur(l, mid, A, B, x) + recur(mid + 1, r, A, B, y))
		return cost
(n, k, A, B) = map(int, input().split())
avengers = list(map(int, input().split()))
print(recur(1, 2 ** n, A, B, avengers))


from sys import setrecursionlimit
setrecursionlimit(1000000000)
(n, k, A, B) = map(int, input().split())
av = [0] + list(map(int, input().split()))
av.sort()

def solve(ss, se):
	(st, en) = (-1, -1)
	(l, h) = (0, k)
	while l <= h:
		m = (l + h) // 2
		if av[m] < ss:
			st = m
			l = m + 1
		else:
			h = m - 1
	(l, h) = (0, k)
	while l <= h:
		m = (l + h) // 2
		if av[m] <= se:
			en = m
			l = m + 1
		else:
			h = m - 1
	na = en - st
	if na == 0:
		return A
	else:
		burn = na * B * (se - ss + 1)
	if ss == se:
		return burn
	x = solve(ss, ss + (se - ss + 1) // 2 - 1)
	y = solve(ss + (se - ss + 1) // 2, se)
	return min(burn, x + y)
print(solve(1, 1 << n))


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
(n, k, A, B) = map(int, input().split())
a = sorted(map(int, input().split()))

def dfs(l, r):
	num = bisect_left(a, r) - bisect_left(a, l)
	q = A if num == 0 else B * num * (r - l)
	if num == 0 or l == r - 1:
		return q
	else:
		mid = (l + r) // 2
		return min(q, dfs(l, mid) + dfs(mid, r))
print(dfs(1, 2 ** n + 1))


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


ii = lambda : int(input())
mi = lambda : 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))


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())

def fnd1(s, e):
	global arr, k
	(l, r) = (0, k - 1)
	ret = -1
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= s:
			r = m - 1
			ret = m
		else:
			l = m + 1
	return ret if arr[ret] <= e else -1

def fnd2(s, e):
	global arr, k
	(l, r) = (0, k - 1)
	ret = -1
	while l <= r:
		m = (l + r) // 2
		if arr[m] <= e:
			l = m + 1
			ret = m
		else:
			r = m - 1
	return ret if arr[ret] >= s else -1

def val(s, e):
	global arr, k, a, b
	if s == 0 or e == 0:
		return 0
	if s == e:
		i = fnd1(s, e)
		if i == -1:
			return a
		else:
			j = fnd2(s, e)
			return b * (j - i + 1)
	else:
		m = (s + e) // 2
		i = fnd1(s, e)
		if i == -1:
			return a
		else:
			j = fnd2(s, e)
			return min(b * (j - i + 1) * (e - s + 1), val(s, m) + val(m + 1, e))
(n, k, a, b) = MI()
arr = sorted(LI())
print(val(1, 2 ** n))


from sys import stdin, setrecursionlimit, stdout
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from heapq import heapify, heappop, heappush, heapreplace, heappushpop

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

def fi():
	return float(stdin.readline())

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

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline().rstrip()

def lsi():
	return list(si())
mod = 1000000007
res = ['NO', 'YES']

def num(start, end):
	ln = k - 1
	(pos, l, r) = (-1, 0, ln)
	while l <= r:
		m = (l + r) // 2
		if a[m] < start:
			pos = m
			l = m + 1
		else:
			r = m - 1
	(pos1, l, r) = (ln + 1, 0, ln)
	while l <= r:
		m = (l + r) // 2
		if a[m] > end:
			pos1 = m
			r = m - 1
		else:
			l = m + 1
	return pos1 - pos - 1

def solve(l, r):
	nm = num(l, r)
	if not nm:
		return x
	if l == r:
		return y * nm
	return min(nm * (r - l + 1) * y, solve(l, (l + r) // 2) + solve((l + r + 2) // 2, r))
test = 1
test_case = 1
while test <= test_case:
	test += 1
	(n, k, x, y) = mi()
	a = sorted(li())
	print(solve(1, 2 ** n))


(n, k, a, b) = map(int, input().split())
avengers = [int(i) for i in input().split()]
avengers.sort()

def get(x, y, avengers):
	if len(avengers) == 0:
		return a
	if x == y:
		return b * len(avengers)
	mid = (x + y) // 2
	left_avengers = []
	right_avengers = []
	for e in avengers:
		if e <= mid:
			left_avengers.append(e)
		else:
			right_avengers.append(e)
	return min(len(avengers) * (y - x + 1) * b, get(x, mid, left_avengers) + get(mid + 1, y, right_avengers))
print(get(1, 2 ** n, avengers))


def rec(l, r, a, A, B):
	if len(a) == 0:
		return A
	cur = len(a) * B * (r - l + 1)
	if l == r:
		return cur
	b = []
	c = []
	mid = (l + r) // 2
	for i in a:
		if i <= mid:
			b.append(i)
		else:
			c.append(i - mid - 1)
	return min(rec(l, mid, b, A, B) + rec(l, mid, c, A, B), cur)
(n, k, A, B) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
	a[i] -= 1
print(rec(0, 2 ** n - 1, a, A, B))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def bs(num):
	low = 0
	high = k - 1
	while low < high:
		mid = (low + high) // 2
		if l[mid] > num:
			high = mid - 1
		else:
			low = mid + 1
	if l[low] > num:
		return low
	else:
		return low + 1

def solve(start, end):
	if start == end:
		if start in d:
			return 1 * b * d[start]
		else:
			return a
	else:
		if start != 0:
			count = bs(end) - bs(start - 1)
		else:
			count = bs(end)
		if count == 0:
			return a
		else:
			temp1 = solve(start, (start + end) // 2)
			temp2 = solve((start + end) // 2 + 1, end)
			return min(temp1 + temp2, b * count * (end - start + 1))
(n, k, a, b) = map(int, input().split())
l = list(map(int, input().split()))
for i in range(k):
	l[i] -= 1
l.sort()
d = {}
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
print(solve(0, 2 ** n - 1))


def solve(l, r, y):
	if len(y) == 0:
		return a
	if l == r:
		return b * len(y)
	c = []
	d = []
	m = (l + r) // 2
	for i in y:
		if i <= m:
			c += [i]
		else:
			d += [i]
	return min(b * (r - l + 1) * len(y), solve(l, m, c) + solve(m + 1, r, d))
(n, k, a, b) = list(map(int, input().split()))
x = list(map(int, input().split()))
print(solve(1, 1 << n, x))


def get(l, r, a):
	global A, B
	if len(a) == 0:
		return A
	if l == r:
		return len(a) * B
	m = (l + r) // 2
	(c, d) = ([], [])
	for x in a:
		if x <= m:
			c += [x]
		else:
			d += [x]
	return min(B * len(a) * (r - l + 1), get(l, m, c) + get(m + 1, r, d))
(n, k, A, B) = map(int, input().split())
a = list(sorted(list(map(int, input().split()))))
print(get(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(sol(1, 2 ** n))


import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, FileIO
sys.stdin = BytesIO(FileIO(0).read())
input = lambda : sys.stdin.readline().rstrip(b'\r\n')

def main():
	(n, k, A, B) = map(int, input().split())
	arr = list(map(int, input().split()))

	def ans(arr, lo, hi):
		if len(arr) == 0:
			return A
		if lo == hi:
			return B * len(arr)
		mi = (lo + hi) // 2
		arr_left = []
		arr_right = []
		for i in range(len(arr)):
			if lo <= arr[i] <= mi:
				arr_left.append(arr[i])
			else:
				arr_right.append(arr[i])
		return min(B * len(arr) * (hi - lo + 1), ans(arr_left, lo, mi) + ans(arr_right, mi + 1, hi))
	FileIO(1, 'w').write(str(ans(arr, 1, 1 << n)).encode())
main()


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

def solve(start, end, positions):
	avg_cnt = len(positions)
	if avg_cnt == 0:
		burn_cost = A
	else:
		burn_cost = B * avg_cnt * (end - start)
	if avg_cnt > 0 and end - start >= 2:
		middle = start + (end - start) // 2
		middle_pos = 0
		for (idx, el) in enumerate(positions):
			if el <= middle:
				middle_pos = idx + 1
			else:
				break
		split_cost = solve(start, middle, positions[:middle_pos]) + solve(middle, end, positions[middle_pos:])
	else:
		split_cost = float('inf')
	if split_cost < burn_cost:
		cost = split_cost
	else:
		cost = burn_cost
	return cost
cost = solve(0, 2 ** n, positions)
print(cost)


from sys import stdin
from bisect import bisect_right, bisect_left
(n, k, a, b) = map(int, input().split())
l = list(map(int, stdin.readline().strip().split()))
l.sort()

def minpower(start, end):
	num = bisect_right(l, end) - bisect_left(l, start)
	if num == 0:
		return a
	elif start == end:
		return b * num
	else:
		mid = (start + end) // 2
		return min(b * num * (end - start + 1), minpower(start, mid) + minpower(mid + 1, end))
print(minpower(1, 1 << n))


(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 sys
input = sys.stdin.readline
import bisect

def rec(l, r):
	left = bisect.bisect_left(base_pos, l)
	right = bisect.bisect(base_pos, r)
	if left == right:
		return a
	if l == r:
		return b * (right - left)
	mid = (l + r) // 2
	return min((right - left) * b * (r - l + 1), rec(l, mid) + rec(mid + 1, r))
(n, k, a, b) = map(int, input().split())
base_pos = [int(i) for i in input().split()]
base_pos.sort()
print(rec(1, 2 ** n))


(n, k, a, b) = map(int, input().split())
from bisect import bisect_right as br
from bisect import bisect_left as bl
p = list(map(int, input().split()))
p.sort()

def dp(i, j, nb):
	if i == j:
		if nb == 0:
			return a
		return nb * b
	if nb == 0:
		c = a
		return c
	else:
		c = b * nb * (j - i + 1)
	r = i + (j - i) // 2
	l = r + 1
	nbl = br(p, r) - bl(p, i)
	nbr = nb - nbl
	return min(c, dp(i, r, nbl) + dp(l, j, nbr))
print(dp(1, 2 ** n, k))


from collections import defaultdict as dd
import math

def nn():
	return int(input())

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

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

def lm():
	return list(map(int, input().split()))
(n, k, A, B) = mi()
avg = lm()

def divide(startbin, endbin, level, currentas, currentlength):
	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)
	a1 = len(astart)
	a2 = len(aend)
	cost1 = (a1 + a2) * B * (binlength * 2)
	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))


import bisect
(n, k, A, B) = list(map(int, input().strip().split()))
positions = sorted(list(map(int, input().strip().split())))

def solve(start, end, positions):
	avg_cnt = len(positions)
	if avg_cnt == 0:
		burn_cost = A
	else:
		burn_cost = B * avg_cnt * (end - start)
	if avg_cnt > 0 and end - start >= 2:
		middle = start + (end - start) // 2
		middle_pos = bisect.bisect_right(positions, middle)
		split_cost = solve(start, middle, positions[:middle_pos]) + solve(middle, end, positions[middle_pos:])
	else:
		split_cost = float('inf')
	if split_cost < burn_cost:
		cost = split_cost
	else:
		cost = burn_cost
	return cost
cost = solve(0, 2 ** n, positions)
print(cost)


n = 0
k = 0
a = 0
b = 0
num = []

def __upper_bound__(val):
	global num
	global k
	l = 0
	r = k - 1
	while l < r:
		mid = l + r >> 1
		if num[mid] < val:
			l = mid + 1
		else:
			r = mid
	if l >= k:
		return l
	if num[l] < val:
		l += 1
	return l

def __dfs__(l, r):
	now = __upper_bound__(r + 1) - __upper_bound__(l)
	if now == 0:
		return a
	if l == r:
		return now * b
	mid = l + r >> 1
	num = __dfs__(l, mid) + __dfs__(mid + 1, r)
	return min(now * b * (r - l + 1), num)

def __solve__():
	line = input().split()
	global n
	n = int(line[0])
	global k
	k = int(line[1])
	global a
	a = int(line[2])
	global b
	b = int(line[3])
	global num
	num = input().split()
	for i in range(k):
		num[i] = int(num[i])
	num.sort(key=None, reverse=False)
	print(__dfs__(1, 1 << n))
__solve__()


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

def rec(l, r):
	numavens = getnums(l, r)
	if numavens == 0:
		return a
	if l == r:
		return b * numavens
	mid = (r - l) // 2 + l
	return min((r - l + 1) * numavens * b, rec(l, mid) + rec(mid + 1, r))

def getnums(l, r):
	if l == 0:
		return get(r)
	return get(r) - get(l - 1)

def get(t):
	l = 0
	r = k - 1
	while l <= r:
		mid = (r - l) // 2 + l
		if x[mid] <= t:
			l = mid + 1
		else:
			r = mid - 1
	return l
(n, k, a, b) = I()
x = I()
x.sort()
l = 1
r = 2 ** n
print(rec(l, r))


def searchlow(arr, l, r, x):
	if arr[-1] < x:
		return -1
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= x:
			r = m - 1
		else:
			l = m + 1
	return r + 1

def searchhigh(arr, l, r, x):
	if arr[0] > x:
		return -1
	while l <= r:
		m = (l + r) // 2
		if arr[m] > x:
			r = m - 1
		else:
			l = m + 1
	return l - 1

def power(low, high):
	high1 = searchhigh(av, 0, len(av) - 1, high)
	low1 = searchlow(av, 0, len(av) - 1, low)
	if high1 == -1 or low1 == -1 or low1 > high1:
		count = 0
	else:
		count = high1 - low1 + 1
	if low == high:
		if count != 0:
			return b * (high - low + 1) * count
		else:
			return a
	if count == 0:
		return a
	else:
		return min(b * count * (high - low + 1), power(low, (low + high) // 2) + power((low + high) // 2 + 1, high))
(n, k, a, b) = list(map(int, input().split()))
av = list(map(int, input().split()))
av.sort()
print(power(1, 2 ** n))


import bisect
import sys
input = sys.stdin.readline
(n, k, A, B) = map(int, input().split())
X = sorted([int(a) - 1 for a in input().split()])

def calc(l, r):

	def cnt(a, b):
		return bisect.bisect_left(X, b) - bisect.bisect_left(X, a)
	c = cnt(l, r)
	if c == 0:
		ret = A
	elif r - l == 1:
		ret = B * c
	else:
		m = (l + r) // 2
		a = cnt(l, m)
		b = c - a
		if a == 0:
			ret = min(A + calc(m, r), B * c * (r - l))
		elif b == 0:
			ret = min(A + calc(l, m), B * c * (r - l))
		else:
			ret = calc(l, m) + calc(m, r)
	return ret
print(calc(0, 2 ** n))


def min_cost(l, r, arr):
	if len(arr) == 0:
		return a
	elif l == r:
		return b * len(arr)
	else:
		m = (l + r) // 2
		back = []
		forw = []
		for i in arr:
			if i <= m:
				back.append(i)
			else:
				forw.append(i)
		return min(b * len(arr) * (r - l + 1), min_cost(l, m, back) + min_cost(m + 1, r, forw))
(n, k, a, b) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
print(min_cost(1, 2 ** n, arr))


def get(tl, tr, a):
	global 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))


import bisect

def calc(l, r):
	index_small = bisect.bisect_left(a, l)
	index_large = bisect.bisect_right(a, r)
	num = index_large - index_small
	if num == 0:
		ans = A
	else:
		ans = B * (r - l + 1) * num
	if l != r and num != 0:
		mid = (l + r - 1) / 2
		ans = min(ans, calc(l, mid) + calc(mid + 1, r))
	return ans
[n, k, A, B] = list(map(int, input().split()))
global a
a = list(map(int, input().split()))
a.sort()
r = 1 << n
print(int(calc(1, r)))


import bisect

def Bin(ot, do):
	return bisect.bisect_right(a, do) - bisect.bisect_left(a, ot)

def rec(l, r):
	kol = Bin(l, r)
	z = x
	if kol > 0:
		z = y * kol * (r - l + 1)
		if l < r:
			z = min(z, rec(l, (l + r) // 2) + rec((l + r) // 2 + 1, r))
	return z
(n, k, x, y) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(rec(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))


def main():
	(n, k, a, b) = 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:
				return a
			else:
				return b * (index_right - index_left + 1)
		if index_left > index_right:
			return a
		interval_mid = interval_left + (interval_right - interval_left) // 2
		(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)
		return min(t0, t1 + t2)
	ret = search(1, 1 << n, 0, k - 1)
	print(ret)
main()


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

def solve(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))


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


import sys
from collections import Counter
from bisect import bisect_left, bisect_right

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

def dinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rtinput():
	return map(float, tinput())

def rec(left, right, q, d, f):
	x = bisect_right(q, right) - bisect_left(q, left)
	if x == 0:
		return d
	if left == right:
		if x == 0:
			return d
		else:
			return f * x
	z = left + right >> 1
	(w, e) = (rec(left, z, q, d, f), rec(z + 1, right, q, d, f))
	return min(f * x * (right - left + 1), w + e)

def main():
	(a, s, d, f) = rinput()
	q = sorted(rinput())
	print(rec(1, 2 ** a, q, d, f))
main()


import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, FileIO
sys.stdin = BytesIO(FileIO(0).read())
input = lambda : sys.stdin.readline().rstrip(b'\r\n')

def main():
	(n, k, A, B) = map(int, input().split())
	a = sorted(map(int, input().split()))

	def solve(lo, hi):
		cnt = bisect_right(a, hi) - bisect_left(a, lo)
		if cnt == 0:
			return A
		if lo == hi:
			return B * cnt
		mi = (lo + hi) // 2
		return min(B * cnt * (hi - lo + 1), solve(lo, mi) + solve(mi + 1, hi))
	FileIO(1, 'w').write(str(solve(1, 2 ** n)).encode())
main()


from bisect import bisect_left, bisect_right
import sys

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

def slv():
	(n, k, A, B) = map(int, input().split())
	avengers = list(map(int, input().split()))
	avengers.sort()

	def get_count(l, r):
		if l >= r:
			return 0
		return bisect_right(avengers, r - 1) - bisect_right(avengers, l - 1)

	def query(L, R):
		assert L <= R
		if L == R:
			cnt = get_count(L, R + 1)
			if cnt:
				return B * cnt
			return A
		else:
			med = (R + L + 1) // 2
			cnt = get_count(L, R + 1)
			if cnt:
				res = B * cnt * (R - L + 1)
			else:
				res = A
				return res
			return min(query(L, med - 1) + query(med, R), res)
	ans = query(1, 1 << n)
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


from math import ceil
from sys import stdin
import bisect
input = stdin.readline

def rec(start, end):
	i = bisect.bisect_left(arr, start, lo=0, hi=len(arr))
	j = bisect.bisect_right(arr, end, lo=0, hi=len(arr))
	avengers = j - i
	power = 0
	if avengers == 0:
		power = A
	else:
		power = B * avengers * (end - start + 1)
	if start == end or avengers == 0:
		return power
	else:
		mid = (start + end) // 2
		return min(rec(start, mid) + rec(mid + 1, end), power)
(n, k, A, B) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr.sort()
start = 1
end = 2 ** n
print(rec(start, end))


import bisect
(n, k, A, B) = map(int, input().split())
X = sorted([int(a) - 1 for a in input().split()])

def calc(l, r, S):
	cl = bisect.bisect_left(S, l)
	cr = bisect.bisect_left(S, r)
	c = cr - cl
	if c == 0:
		ret = A
	elif r - l == 1:
		ret = B * c
	else:
		m = (l + r) // 2
		cm = bisect.bisect_left(S, m)
		a = cm - cl
		b = cr - cm
		SL = []
		SR = []
		for s in S:
			if s < m:
				SL.append(s)
			else:
				SR.append(s)
		if a == 0:
			ret = min(A + calc(m, r, SR), B * c * (r - l))
		elif b == 0:
			ret = min(A + calc(l, m, SL), B * c * (r - l))
		else:
			ret = calc(l, m, SL) + calc(m, r, SR)
	return ret
print(calc(0, 2 ** n, X))


(n, k, A, B) = map(int, input().split())
avg = [int(i) for i in input().split()]
avg.sort()

def get(x, y, a):
	if len(a) == 0:
		return A
	elif x == y:
		return B * len(a)
	else:
		mid = (x + y) // 2
		left = []
		right = []
		for i in a:
			if i <= mid:
				left.append(i)
			else:
				right.append(i)
		return min(len(a) * (y - x + 1) * B, get(x, mid, left) + get(mid + 1, y, right))
print(get(1, 2 ** n, avg))


(n, k, a, b) = list(map(int, input().split()))
h = [0] + list(map(int, input().split()))
h.sort()

def binp(nu):
	l = 0
	r = len(h) - 1
	while r - l > 1:
		if h[(l + r) // 2] > nu:
			r = (l + r) // 2
		else:
			l = (l + r) // 2
	if h[r] <= nu:
		return l + 1
	else:
		return l

def rec(start, stop, a, b):
	g = binp(start - 1)
	f = binp(stop)
	if g == f:
		return a
	elif stop - start == 0:
		return b * (f - g)
	else:
		return min((stop - start + 1) * (f - g) * b, rec(start, stop - (stop - start + 1) // 2, a, b) + rec(stop - (stop - start + 1) // 2 + 1, stop, a, b))
print(rec(1, 2 ** n, a, b))


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


from bisect import bisect, bisect_left

def rec(i, j):
	x = bisect(ar, j) - bisect_left(ar, i)
	if x == 0:
		return a
	if i == j:
		return b * x
	m = i + j >> 1
	return min(b * (j - i + 1) * x, rec(i, m) + rec(m + 1, j))
(n, k, a, b) = map(int, input().split())
ar = list(map(int, input().split()))
ar.sort()
print(rec(1, 2 ** n))


(n, k, A, B) = [int(e) for e in input().split()]
power = tuple([int(e) for e in input().split()])
memo = {}

def solve(n, k):
	if n == 0 and len(k) == 0:
		return A
	elif n == 0:
		return B * len(k)
	if len(k) != 0:
		opt1 = B * len(k) * (1 << n)
	else:
		opt1 = A
	ref = 1 << n - 1
	kl = tuple([e for e in k if e <= ref])
	kr = tuple([e - ref for e in k if e > ref])
	if (n, kl) in memo:
		l = memo[n, kl]
	else:
		tmp = solve(n - 1, kl)
		memo[n, kl] = tmp
		l = tmp
	if (n, kr) in memo:
		r = memo[n, kr]
	else:
		tmp = solve(n - 1, kr)
		memo[n, kr] = tmp
		r = tmp
	opt2 = l + r
	return min(opt1, opt2)
print(solve(n, power))


import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, FileIO
sys.stdin = BytesIO(FileIO(0).read())
input = lambda : sys.stdin.readline().rstrip(b'\r\n')

def main():

	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.append(el)
			if mid + 1 <= el <= r:
				arr_right.append(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) = map(int, input().split())
	arr = [int(i) - 1 for i in input().split()]
	FileIO(1, 'w').write(str(ans(arr, 0, (1 << n) - 1, a, b)).encode())
main()


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


from sys import stdin, stdout
from math import *
from heapq import *
from collections import *

def power(L, R, a):
	global A, B
	if L == R:
		if len(a) == 0:
			return A
		else:
			return B * len(a)
	if len(a) == 0:
		return A
	l = []
	r = []
	mid = floor((L + R) / 2)
	for x in a:
		if x <= mid:
			l.append(x)
		else:
			r.append(x)
	return min(len(a) * B * (R - L + 1), power(L, mid, l) + power(mid + 1, R, r))

def main():
	global n, k, A, B
	(n, k, A, B) = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	stdout.write(str(power(1, 1 << n, a)))
	return 0
main()


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


from sys import stdin
(n, k, a, b) = map(int, input().split())
l = list(map(int, stdin.readline().strip().split()))
l.sort()

def minpower(start, end, array):
	global a, b
	length = len(array)
	if length == 0:
		return a
	elif start == end:
		return b * length
	else:
		mid = (start + end) // 2
		left = []
		right = []
		for i in array:
			if start <= i <= mid:
				left.append(i)
			elif mid < i <= end:
				right.append(i)
		return min(b * length * (end - start + 1), minpower(start, mid, left) + minpower(mid + 1, end, right))
print(minpower(1, 1 << n, l))


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

def bs(l, r, val, a):
	l1 = l
	r1 = r
	res = -1
	while l1 <= r1:
		mid = (l1 + r1) // 2
		if a[mid] <= val:
			res = mid
			l1 = mid + 1
		else:
			r1 = mid - 1
	return res

def bsfl(l, r, val, a):
	l1 = l
	r1 = r
	res = -1
	while l1 <= r1:
		mid = (l1 + r1) // 2
		if a[mid] < val:
			l1 = mid + 1
		elif a[mid] >= val:
			res = mid
			r1 = mid - 1
	return res

def split(left, right, a):
	l1 = bsfl(0, k - 1, left, a)
	if a[l1] > right:
		l1 = -1
	r1 = bs(0, k - 1, right, a)
	if a[r1] < left:
		r1 = -1
	if r1 == -1 or l1 == -1:
		return A
	if left == right:
		res = B * (right - left + 1) * (r1 - l1 + 1)
		return res
	res = min(B * (right - left + 1) * (r1 - l1 + 1), split(left, (right + left) // 2, a) + split((right + left) // 2 + 1, right, a))
	return res
a.sort()
print(split(1, 2 ** n, a))