1s 512M

题目描述

小明这天在参加公司团建，团建项目是爬山。在 $x$ 轴上从左到右一共有 $n$ 座山，第 $i$ 座山的高度为 $h_i$。他们需要从左到右依次爬过所有的山，需要花费的体力值为 $S= \sum_{i=1}^nh_i$。

然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 $H$ 的山的高度变为 $\lfloor\sqrt{ H }\rfloor$，可以使用 $P$ 次；第二种魔法可以将高度为 $H$ 的山的高度变为 $\left\lfloor\frac{H}{2}\right\rfloor$ ，可以使用 $Q$ 次。并且对于每座山可以按任意顺序多次释放这两种魔法。

小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少。

输入格式

输入共两行。
第一行为三个整数 $n$，$P$，$Q$。
第二行为 $n$ 个整数 $h_1$，$h_2$，...，$h_n$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

4 1 1
4 5 6 49

输出 #1

18

说明/提示

• 对 $20\%$ 的数据，$n \leq 8$，$P = 0$。
• 对全部的测试数据，保证 $1 \leq n \leq 10^5$，$0 \leq P, Q \leq n$，$0 \leq h_i \leq 10^5$。