P15022

买干草

难度 5 级 小学 动态规划入门 背包DP
讨论 统计 22通过 52提交 42.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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 如何在不超过马车最大容积的情况下买到最大体积的稻草?他不可以把一捆稻草分开来买。

输入

第一行两个整数,分别为 C 和 H。

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

输出

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

样例

样例 1
输入
7 3 
2 
6 
5
输出
7

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交