返回小组 开始 2026-08-24 13:30:00

0-1背包专题(8.24下午)

结束 2026-08-24 15:00:00
Contest is over.
当前 2026-09-03 17:39:36

B. 买干草

描述

Farmer John 面临一个很可怕的事,因为疏于防范,他存储的所有稻草都被澳洲蟑螂吃光了,他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前,John 拉着他的马车到农民 Don 的农场中买一些稻草给奶牛过冬。已知 John 的马车可以装的下 C(1\le C\le5\times10^4) 立方的稻草。

农民 Don 有 H(1\le H\le5\times10^3) 捆体积不同的稻草可供购买,每一捆稻草有它自己的体积 V_i( V_i\le C)。面对这些稻草 John 认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。

现在给定马车的最大容积 C 和每一捆稻草的体积 V_i,John 如何在不超过马车最大容积的情况下买到最大体积的稻草?他不可以把一捆稻草分开来买。

输入

第一行两个整数,分别为 CH

2H+1 行:每一行一个整数代表第 i 捆稻草的体积 V_i

输出

一个整数,为 John 能买到的稻草的体积。

样例

输入

7 3 
2 
6 
5

输出

7

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交