{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"Kiana 喜欢吃甜点,某天她从商店中买回来 $N$ 块切糕与 Tinytree 共同分享,其中第 $i$ 块切糕的大小用一个数 $A_i$ 来表示。\n\n因为每块切糕的风味都不同,所以 Kiana 和 Tinytree 决定将每块切糕都切成两份,两人各选一份品尝。但切切糕是一个自古以来的大难题,经过商议,Kiana 打算执刀来切切糕,而 Tinytree 有 $M$ 次“优先选糕权”,可以获得一些切糕切开后的优先选择权,具体来说,两人按照如下流程进行操作:\n\n步骤一:Kiana 从还没切的切糕中按自己的想法选一块出来,并将其切成两份,其中**每份切糕的大小可以是任意正实数,也可以是 $\\mathbf{0}$,且两份切糕的大小之和与切之前的大小相同**。\n\n步骤二:Tinytree 观察完 Kiana 切出的两份切糕大小后,如果还有“优先选糕权”次数剩余,则可以决定是否消耗 $1$ 次“优先选糕权”来进行优先选择。\n\n步骤三:如果 Tinytree 选择使用“优先选糕权”,则她可以从两份切糕中任选一份,另一份则归 Kiana,如果 Tinytree 选择不使用或者已经用完了 $M$ 次“优先选糕权”,则 Kiana 从两份切糕中任选一份,另一份则归 Tinytree,然后两人回到步骤一,直到所有的切糕都切完。\n\n假设 Kiana 和 Tinytree 都足够聪明,在自己可以操作时总是想办法**让自己最终获得的切糕总大小尽可能大**,且开始切第一块切糕之前 $N$ 块切糕的大小是两人都已知的,“优先选糕权”不要求全部用完。现在 Kiana 想知道,自己能获得的切糕总大小是多少,由于 Kiana 自己不会算,所以希望你能够帮助她。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含两个正整数 $N$ 和 $M$($1 \\le M \\le N \\le 2500$),分别表示切糕的总数和 Tinytree 初始时“优先选糕权”的次数。 \n第二行包含 $N$ 个正整数,其中第 $i$ 个数 $A_i$($1 \\le A_i \\le 50000$)表示第 $i$ 块切糕的大小。"}},{"title":"Output","value":{"format":"MD","content":"输出共一行,包含一个实数,表示**Kiana 最终能获得的切糕总大小**,所有输出精确到小数点后六位。"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\n4 3 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5.250000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"**【样例解释 #1】**\n\n在这个样例中总共有 $4$ 块切糕,大小分别为 $4,3,2,1$,Tinytree 的“优先选糕权”一共有三次,两人可以按照如下顺序和方式来分配切糕:\n\n第一块:Kiana 选择大小为 $3$ 的切糕,将其切成大小为 $1.25$ 和 $1.75$ 的两部分,Tinytree 使用一次“优先选糕权”选走 $1.75$ 的部分,Kiana 目前总共获得大小 $1.25$ 的切糕。\n\n第二块:Kiana 选择大小为 $1$ 的切糕,将其切成大小为 $0$ 和 $1$ 的两部分,Tinytree 不使用“优先选糕权”,Kiana 独得此糕,目前总共获得大小 $2.25$ 的切糕。\n\n第三块:Kiana 选择大小为 $2$ 的切糕,将其切成大小为 $1$ 和 $1$ 的两部分,Tinytree 使用一次“优先选糕权”选走 $1$ 的部分,Kiana 目前总共获得大小 $3.25$ 的切糕。\n\n第四块:Kiana 选择大小为 $4$ 的切糕,将其切成大小为 $2$ 和 $2$ 的两部分,Tinytree 使用一次“优先选糕权”选走 $2$ 的部分,Kiana 目前总共获得大小 $5.25$ 的切糕。\n\n综上所述,该样例输出 $5.250000$,且可以证明在这个方案中如果任意一人改变自己的策略,其获得的切糕总大小不可能变得更大。\n\n**【题目来源】**\n\n来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。\n\n题解等资源可在 \u003chttps://github.com/THUSAAC/THUPC2021-pre\u003e 查看。"}}]}