[THUPC2021 初赛] 切切糕

Kiana 喜欢吃甜点，某天她从商店中买回来 $N$ 块切糕与 Tinytree 共同分享，其中第 $i$ 块切糕的大小用一个数 $A_i$ 来表示。 因为每块切糕的风味都不同，所以 Kiana 和 Tinytree 决定将每块切糕都切成两份，两人各选一份品尝。但切切糕是一个自古以来的大难题，经过商议，Kiana 打算执刀来切切糕，而 Tinytree 有 $M$ 次“优先选糕权”，可以获得一些切糕切开后的优先选择权，具体来说，两人按照如下流程进行操作： 步骤一：Kiana 从还没切的切糕中按自己的想法选一块出来，并将其切成两份，其中**每份切糕的大小可以是任意正实数，也可以是 $\mathbf{0}$，且两份切糕的大小之和与切之前的大小相同**。 步骤二：Tinytree 观察完 Kiana 切出的两份切糕大小后，如果还有“优先选糕权”次数剩余，则可以决定是否消耗 $1$ 次“优先选糕权”来进行优先选择。 步骤三：如果 Tinytree 选择使用“优先选糕权”，则她可以从两份切糕中任选一份，另一份则归 Kiana，如果 Tinytree 选择不使用或者已经用完了 $M$ 次“优先选糕权”，则 Kiana 从两份切糕中任选一份，另一份则归 Tinytree，然后两人回到步骤一，直到所有的切糕都切完。 假设 Kiana 和 Tinytree 都足够聪明，在自己可以操作时总是想办法**让自己最终获得的切糕总大小尽可能大**，且开始切第一块切糕之前 $N$ 块切糕的大小是两人都已知的，“优先选糕权”不要求全部用完。现在 Kiana 想知道，自己能获得的切糕总大小是多少，由于 Kiana 自己不会算，所以希望你能够帮助她。

第一行包含两个正整数 $N$ 和 $M$（$1 \le M \le N \le 2500$），分别表示切糕的总数和 Tinytree 初始时“优先选糕权”的次数。 第二行包含 $N$ 个正整数，其中第 $i$ 个数 $A_i$（$1 \le A_i \le 50000$）表示第 $i$ 块切糕的大小。

输出共一行，包含一个实数，表示**Kiana 最终能获得的切糕总大小**，所有输出精确到小数点后六位。

4 3
4 3 2 1

5.250000

**【样例解释 #1】** 在这个样例中总共有 $4$ 块切糕，大小分别为 $4,3,2,1$，Tinytree 的“优先选糕权”一共有三次，两人可以按照如下顺序和方式来分配切糕： 第一块：Kiana 选择大小为 $3$ 的切糕，将其切成大小为 $1.25$ 和 $1.75$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1.75$ 的部分，Kiana 目前总共获得大小 $1.25$ 的切糕。 第二块：Kiana 选择大小为 $1$ 的切糕，将其切成大小为 $0$ 和 $1$ 的两部分，Tinytree 不使用“优先选糕权”，Kiana 独得此糕，目前总共获得大小 $2.25$ 的切糕。 第三块：Kiana 选择大小为 $2$ 的切糕，将其切成大小为 $1$ 和 $1$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1$ 的部分，Kiana 目前总共获得大小 $3.25$ 的切糕。 第四块：Kiana 选择大小为 $4$ 的切糕，将其切成大小为 $2$ 和 $2$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $2$ 的部分，Kiana 目前总共获得大小 $5.25$ 的切糕。 综上所述，该样例输出 $5.250000$，且可以证明在这个方案中如果任意一人改变自己的策略，其获得的切糕总大小不可能变得更大。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。