Description

Kiana likes desserts. One day, she bought $N$ cutcakes from a store and shared them with Tinytree. The size of the $i$-th cutcake is represented by a number $A_i$.

Since each cutcake has a different flavor, Kiana and Tinytree decide to cut each cutcake into two parts, and each person chooses one part to taste. However, cutting cutcakes is a difficult problem that has existed since ancient times. After discussion, Kiana will do the cutting, and Tinytree has $M$ chances of “priority choosing rights”, which allow her to have priority to choose after a cut. Specifically, they operate as follows:

Step 1: Kiana chooses one uncut cutcake in any way she wants, and cuts it into two parts. The size of each part can be any positive real number, or can be $\mathbf{0}$, and the sum of the two parts equals the size before cutting.

Step 2: After observing the sizes of the two parts cut by Kiana, if Tinytree still has remaining “priority choosing rights”, she may decide whether to spend $1$ “priority choosing right” to make a priority choice.

Step 3: If Tinytree chooses to use a “priority choosing right”, she can choose either part, and the other part goes to Kiana. If Tinytree chooses not to use it, or she has already used up all $M$ “priority choosing rights”, then Kiana chooses either part, and the other part goes to Tinytree. Then they return to Step 1 until all cutcakes have been cut.

Assume both Kiana and Tinytree are smart enough: whenever it is their turn to act, they always try to maximize the final total size of cutcakes they obtain. Also, before cutting the first cutcake, the sizes of all $N$ cutcakes are known to both of them. Tinytree does not have to use up all “priority choosing rights”. Now Kiana wants to know the total size of cutcakes she can obtain. Since Kiana cannot compute it herself, she asks you to help.

Input Format

The first line contains two positive integers $N$ and $M$ ($1 \le M \le N \le 2500$), representing the total number of cutcakes and the initial number of Tinytree’s “priority choosing rights”, respectively.
The second line contains $N$ positive integers. The $i$-th number $A_i$ ($1 \le A_i \le 50000$) represents the size of the $i$-th cutcake.

Output Format

Output one line containing a real number, representing the final total size of cutcakes that Kiana can obtain. All outputs should be accurate to six digits after the decimal point.

4 3
4 3 2 1

5.250000

Hint

Sample Explanation #1.

In this sample, there are $4$ cutcakes with sizes $4,3,2,1$. Tinytree has three “priority choosing rights”. They can distribute the cutcakes in the following order and manner:

First cutcake: Kiana chooses the cutcake of size $3$ and cuts it into two parts of sizes $1.25$ and $1.75$. Tinytree uses one “priority choosing right” and takes the part of size $1.75$. Kiana has obtained a total size of $1.25$ so far.

Second cutcake: Kiana chooses the cutcake of size $1$ and cuts it into two parts of sizes $0$ and $1$. Tinytree does not use a “priority choosing right”, and Kiana takes the whole cutcake. Kiana has obtained a total size of $2.25$ so far.

Third cutcake: Kiana chooses the cutcake of size $2$ and cuts it into two parts of sizes $1$ and $1$. Tinytree uses one “priority choosing right” and takes the part of size $1$. Kiana has obtained a total size of $3.25$ so far.

Fourth cutcake: Kiana chooses the cutcake of size $4$ and cuts it into two parts of sizes $2$ and $2$. Tinytree uses one “priority choosing right” and takes the part of size $2$. Kiana has obtained a total size of $5.25$ so far.

Therefore, the output for this sample is $5.250000$. It can also be proven that under this plan, if either person changes their strategy, their final total size of cutcakes cannot become larger.

Source of the Problem.

From the preliminary round of the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational Contest (THUPC2021).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5