Problem Description

This problem is suspected to be incorrect. So far, there is no algorithm that can produce the correct solution for all inputs within the given time limit.

Xiaoming is taking part in a company team-building activity, and the activity is mountain climbing. On the $x$ axis, there are $n$ mountains from left to right. The height of the $i$-th mountain is $h_i$. They need to climb all the mountains from left to right in order, and the stamina cost is $S = \sum_{i=1}^n h_i$.

However, Xiaoming secretly learned magic that can reduce the heights of some mountains. He knows two types of magic. The first type can change the height of a mountain with height $H$ to $\lfloor\sqrt{ H }\rfloor$, and it can be used $P$ times. The second type can change the height of a mountain with height $H$ to $\left\lfloor\frac{H}{2}\right\rfloor$, and it can be used $Q$ times. For each mountain, these two types of magic can be cast multiple times in any order.

Xiaoming wants to plan which mountains to use magic on so that the stamina cost of climbing is minimized. What is the minimum possible stamina cost in the optimal case?

Input Format

The input has two lines.
The first line contains three integers $n$, $P$, $Q$.
The second line contains $n$ integers $h_1$, $h_2$, $\ldots$, $h_n$.

Output Format

Output one line with one integer, which is the answer.

4 1 1
4 5 6 49

18

Hint

• For $20\%$ of the testdata, $n \leq 8$, $P = 0$.
• For all testdata, it is guaranteed that $1 \leq n \leq 10^5$, $0 \leq P, Q \leq n$, $0 \leq h_i \leq 10^5$.

Translated by ChatGPT 5