#996. 背包问题

背包问题

问题描述

有 N 个物品,第 i 个物品的重量为 Wi。现在想将一些物品装入到一个背包里,背包的最大载重量为 M。

问:能装入背包的物品的总重量最大是多少?

输入格式

第一行:两个整数 M、N;

接下来 N 行:每行一个整数 Wi。

输出格式

一个整数,表示答案。

输入样例

10 3
3
4
5

输出样例

9

数据范围

20% 的数据:1 ≤ N ≤ 10

100% 的数据:1 ≤ N ≤ 48, 1 ≤ M, Wi ≤ 231−12^{31}-1