Creative Snap

## 题目描述 灭霸要摧毁复仇者们的基地！ 我们可以将复仇者的基地看成一个序列，每个位置都有可能有多个复仇者；但是每个复仇者只能占据一个位置。 他们基地的长度刚好是$2$的整数幂，灭霸想要用最少的能量摧毁它们。他在摧毁过程中，可以选择： - 如果这段基地长度$\ge 2$，他可以将其分为相等长度的两半。 - 烧掉这段基地。如果这段基地中没有复仇者，他需要消耗$A$的能量；如果有，则需要消耗$B*x*l$的能量。其中$l$是这段基地长度，$x$是这段中的复仇者数量。 输出一个整数，表示他摧毁全部基地需要的最少能量。 ## 输入输出格式 ### 输入格式 第一行四个整数$n,k,A,B$；$2^n$为基地长度，$k$是总共的复仇者数量，$A,B$的意义如题目描述。 接下来一行$k$个整数，$a_i$表示第$i$个复仇者所在的位置 ### 输出格式 一个整数，表示摧毁基地所需要的最少能量。 ## 说明 ### 样例解释 对于样例1，直接烧区间$[1,4]$需要能量为$4*2*2=16$。 但是，如果将其分为$4$段，分别烧掉，所需能量只有$2+1+2+1=6$。 可以证明没有更优的方案，所以输出`6`。 ### 数据范围 对于全部数据： $1\le n \le 30$ $1\le k \le 10^5$ $1\le A,B \le 10^4$ $1\le a_i \le 2^n$

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.

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 one integer — the minimum power needed to destroy the avengers base.

2 2 1 2
1 3

6

3 2 1 2
1 7

8

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