logo AlgoBeat OnlineJudge
登录 注册

#213636. [KOI 2025 #2] 包

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。


商户是在 KOI 市经营商店的一位市民。商户的店里有 件商品,其中第 件商品的重量为 。商户收到了情报,得知小偷“金基范”正觊觎自己的店铺,于是他准备采取措施,将损失降到最低。

小偷金基范计划从店里偷走 件商品。但如果商品太重,不仅难以偷窃,被警察抓住的可能性也会变高。因此,小偷金基范会最小化他所偷商品的总重量。不过,如果店里的商品总数不足 件,小偷金基范会偷走店里所有的商品。

在小偷金基范到达店铺之前,商户会把店里的一些商品装进一个包里带走。之后,小偷金基范会对商户没有带走的那些商品,以上述方式实施盗窃。商户希望通过合理地往包里装商品,来最大化小偷金基范最终偷走的商品总重量。

商户的包能承受的重量是有限的。当给定一个最大承重 时,请对所有的 回答以下问题:

  • 在商户能放入包中的商品总重量不超过 的条件下,小偷金基范偷走的商品总重量的最大值是多少?

输入格式

第一行给定 ,由空格分隔。

第二行给定 个整数 ,由空格分隔。

输出格式

输出 行。第 行输出当 时,小偷金基范偷走的商品总重量的最大值。

样例

样例输入 1

5 1 6
1 2 3 4 5

样例输出 1

2
2
3
3
3
4

样例输入 2

5 2 5
2 3 5 7 11

样例输出 2

5
8
8
8
12

样例输入 3

3 2 3
1 1 7

样例输出 3

8
8
8

数据范围与提示

限制条件

  • 所有给定的数都是整数。
  • 对于所有 (),满足

子任务

  1. (13 分)
  2. (17 分)
  3. (23 分)
  4. (16 分)
  5. (31 分) 无额外限制条件。