#662. [USACO08DEC]Hay For Sale S

[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