C. Creative Snap

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 22. 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 22, divide the base into 22 equal halves and destroy them separately, or
  • burn the current base. If it contains no avenger in it, it takes AA amount of power, otherwise it takes his B⋅na⋅lB⋅na⋅l amount of power, where nana is the number of avengers and ll 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 nn, kk, AA and BB (1≤n≤301≤n≤30, 1≤k≤1051≤k≤105, 1≤A,B≤1041≤A,B≤104), where 2n2n is the length of the base, kk is the number of avengers and AA and BB are the constants explained in the question.

The second line contains kk integers a1,a2,a3,…,aka1,a2,a3,…,ak (1≤ai≤2n1≤ai≤2n), where aiai 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

题意：灭霸要毁灭所有的复仇者基地，每个基地可能有一个或多个复仇者看守，也可能没有人。复仇者基地相连，灭霸从所有基地开始，当他选择了两个或以上的一段基地时，可以将其分成两等份分别毁灭；若其中没有复仇者，则花费A的力量就能将其全部毁灭；若有复仇者，则需要花费B*复仇者的数目*基地的长度 的力量。求出灭霸毁灭所有基地需要的最小力量。

二分+递归，记录所有复仇者所在基地的位置，并进行排序，利用 upper_bound( r )-lower_bound( l ) 就可以求出从基地 l 到基地 r 一共有多少名复仇者。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[100005];
ll n,k,A,B;

ll dfs(int l,int r)
{
	int m=l+(r-l+1)/2;
	ll sum;
	int num=upper_bound(a+1,a+k+1,r)-lower_bound(a+1,a+k+1,l);
	if(num==0)
		sum=A;
	else
	{
		sum=B*num*(r-l+1);
		if(r-l>=1)
			sum=min(sum,dfs(l,m-1)+dfs(m,r));
	}	
	return sum;
}

int main()
{
	int i;
	cin>>n>>k>>A>>B;
	for(i=1;i<=k;i++)
		cin>>a[i];
	sort(a+1,a+k+1);
	cout<<dfs(1,1<<n)<<endl;
	return 0;
}