P0846

[Usaco2008 Dec]Hay For Sale 购买干草

[Usaco2008 Dec]Hay For Sale 购买干草

约翰遭受了重大损失:蟑螂吃掉了他所有的干草,留下一群饥饿的奶牛。于是,他驾驶一辆容量为 CC 个体积单位的马车,前往顿因家购买干草。

顿因有 HH 包干草,第 ii 包干草的体积为 ViV_i。约翰只能整包购买干草。请计算他最多能运回多少体积的干草。

输入格式

第一行包含两个整数 CC 和 HH,分别表示马车的容量和干草的包数。

接下来 HH 行,每行包含一个整数 ViV_i,表示第 ii 包干草的体积。

输出格式

输出一个整数,表示约翰最多能够运回的干草体积。

样例输入

7 3
2
6
5

样例输出

7

样例解释

购买体积分别为 22 和 55 的两包干草,恰好装满容量为 77 的马车,因此最多可以运回体积为 77 的干草。

数据范围

  • 1≤C≤500001\le C\le 50000;
  • 1≤H≤50001\le H\le 5000;
  • 1≤Vi≤C1\le V_i\le C。

来源与许可

本题为 USACO 2008 December 试题「Hay For Sale(购买干草)」,题面与测试数据整理自 BZOJ。

样例 1

输入

7 3
2
6
5

输出

7