#H. [USACO08DEC]Hay For Sale S

    传统题 1000ms 256MiB

[USACO08DEC]Hay For Sale S

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

希蒙面临一个很可怕的事实,因为防范失措他存储的所有稻草给大蟑螂吃光了,他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前,希蒙拉着他的马车到蒙蒙的农场中买一些稻草给奶牛过冬。已知希蒙的马车可以装的下C(1<=C<=50,000)C(1 <= C <=50,000)立方的稻草。

蒙蒙有H(1<=H<=5,000)H(1 <= H <= 5,000)捆体积不同的稻草可供购买,每一捆稻草有它自己的体积(1<=Vi<=C)(1 <= V_i <= C)。面对这些稻草希蒙认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。 现在给定马车的最大容积CC和每一捆稻草的体积ViVi,希蒙如何在不超过马车最大容积的情况下买到最大体积的稻草?他不可以把一捆稻草分开来买

输入格式

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

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

输出格式

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

样例

输入样例

7 3 
2 
6 
5

输出样例

7

数据范围与提示

1<=C<=50,000 1 <= C <=50,000

1<=H<=5,000 1 <= H <= 5,000

11<=Vi<=C 11 <= V_i <= C

背包

未认领
状态
已结束
题目
9
开始时间
2022-2-19 12:00
截止时间
2022-2-26 8:00
可延期
0 小时