灭霸想要摧毁复仇者联盟基地,但他需要摧毁复仇者联盟和他们的基地。
让我们用一个数组来表示他们的基地,其中每个位置可以被许多复仇者占据,但一个复仇者只能占据一个位置。它们的底座长度是 $$$2$$$ 的完美幂。灭霸想要用最小的力量摧毁基地。他从整个基地开始,一步一步可以执行以下任一操作:
- 如果当前长度至少为 $$$2$$$,则将底座分成 $$$2$$$ 相等的两半并分别销毁,或者
- 烧毁当前基地。如果其中不包含复仇者,则需要 $$$A$$$ 的力量,否则需要 $$$B \cdot n_a \cdot l$$$ 的力量,其中 $$$n_a$$$ 是复仇者的数量,$$$l$$$ 是当前基地的长度。
输入
第一行包含四个整数 $$$n$$$、$$$k$$$、$$$A$$$ 和 $$$B$$$ ($$$1 \leq n \leq 30$$$、$$$1 \leq k \leq 10^5$$$、$$$1 \leq A,B \leq 10^4$$$),其中$$$2^n$$$ 是基数的长度,$$$k$$$ 是复仇者的数量,$$$A$$$ 和 $$$B$$$ 是问题中解释的常量。
第二行包含$$$k$$$整数$$$a_{1}, a_{2}, a_{3}, \ldots, a_{k}$$$ ($$$1 \leq a_{i} \leq 2^n$$$),其中$$$a_{i}$$$表示复仇者在基地中的位置。
输出
输出一个整数——摧毁复仇者联盟基地所需的最小力量。
示例
输入 #1
2 2 1 2 1 3
输出 #1
6
输入 #2
3 2 1 2 1 7
输出 #2
8
注意
考虑第一个例子。
Thanos 的一个选择是用能量 $$$2 \cdot 2 \cdot 4 = 16$$$ 烧掉整个基地 $$$1-4$$$。
否则他可以将底座分为两部分$$$1-2$$$和$$$3-4$$$。
对于基础 $$$1-2$$$,他可以用能量 $$$2 \cdot 1 \cdot 2 = 4$$$ 将其燃烧,或者将其分成 $$$2$$$ 部分 $$$1-1$$$ 和 $$$2-2$$$。
对于基础 $$$1-1$$$,他可以用能量 $$$2 \cdot 1 \cdot 1 = 2$$$ 来燃烧它。对于 $$$2-2$$$,他可以用 $$$1$$$ 的力量摧毁它,因为没有复仇者。因此,摧毁 $$$1-2$$$ 的总力量为 $$$2 + 1 = 3$$$,小于 $$$4$$$。
同样,他需要$$$3$$$力量来摧毁$$$3-4$$$。所需的最低总功率为 $$$6$$$。