3333. [USACO20 Jan Silver]Berry Picking

【题目描述】

Bessie 和她的妹妹 Elsie 正在 Farmer John 的浆果园里采浆果。Farmer John 的浆果园里有 $N$ 棵浆果树（$1\le N\le 1000$）；树 $i$ 上有 $B_i$ 个浆果（$1\le B_i\le 1000$）。Bessie 有 $K$ 个篮子（$1 \le K \le 1000$，$K$ 为偶数）。每个篮子里可以装同一棵树上采下的任意多个浆果，但是不能装来自于不同的树上的浆果，因为它们的口味可能不同。篮子里也可以不装浆果。

Bessie 想要使得她得到的浆果数量最大。但是，Farmer John 希望 Bessie 与她的妹妹一同分享，所以 Bessie 必须将浆果数量较多的 $\frac{K}{2}$ 个篮子给 Elsie。这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果，这十分不公平，然而姐妹之间往往就是这样。

帮助 Bessie 求出她最多可以得到的浆果数量。

【输入格式】

输入的第一行包含以空格分隔的整数$ N $和$ K $。

第二行包含$ N $以空格分隔的整数$ B_1 ， B_2，…，B_N $。

【输出格式】

只有一个整数，即 Bessie 可以收集的最大浆果数量。

【样例输入】

5 4
3 6 8 4 2

【样例输出】

8

【样例解释】

如果Bessie用第 2 棵树上的 6 个浆果装满一个篮子

另用两个篮子分别装来自第 3 棵树上的 4 个浆果

再用一个篮子装第 4 棵树上的 4 个浆果

最后她收到两个带有 4 个浆果的篮子，总共收集了 8 个浆果。

【提示】

对于$ 37\% $的测试数据(测试点$ 1\sim4 $)，满足$ K ≤ 10 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Silver 组