Berry Picking

题目描述

贝茜和她的妹妹艾尔茜正在约翰农夫的浆果园里采摘浆果。约翰农夫的浆果园里恰好有 $N$ 棵浆果树（$1\le N\le 1000$）；第 $i$ 棵树上恰好有 $B_i$ 颗浆果（$1\le B_i\le 1000$）。贝茜有恰好 $K$ 个篮子（$1 \le K \le 1000$, $K$ 为偶数）。每个篮子可以装来自同一棵树的任意数量的浆果（由贝茜决定），但不能同时装来自两棵不同树的浆果，因为它们的味道会互相冲突。篮子也可以留空。 贝茜想要最大化她收集到的浆果数量。然而，约翰农夫希望贝茜与妹妹分享，因此贝茜必须把装有浆果数量最多的 $K/2$ 个篮子给艾尔茜。这意味着艾尔茜最终得到的浆果甚至可能比贝茜还多，这非常不公平，但不幸的是，兄弟姐妹之间的相处并不总是公平的。 请帮助贝茜计算她最多能收集到多少浆果。

输入格式

第一行输入包含用空格分隔的整数 $N$ 和 $K$。 第二行包含 $N$ 个用空格分隔的整数 $B_1,B_2,\ldots,B_N.$

输出格式

输出一行答案。

5 4
3 6 8 4 2

8

提示

计分： 测试点 1-4 满足 $K\le 10.$ 测试点 5-11 没有额外限制。 如果贝茜装： 一个篮子装第 2 棵树的 6 颗浆果 两个篮子，每个装第 3 棵树的 4 颗浆果 一个篮子装第 4 棵树的 4 颗浆果 那么她会得到两个各装 4 颗浆果的篮子，总共得到 8 颗浆果。 题目来源：Nathan Pinsker

标签: USACO|2020|Silver

来源

USACO|2020|Silver