超大背包容量最大和

题目描述:

给出 N( N ≤ 46 ) 个物品的重量，以及一个容量为$W(1\le W\le 2^{31})$  的背包，求在背包容量范围内一次性能装入的最大重量。

输入格式:

第一行两个整数W 和 n。

第二行 n 个整数表示每个物品的重量，每个物品重量 $1\le a_i\le 2^{31}$ 

输出格式:

一个整数表示答案。

样例输入:

20 5
7 5 4 18 1

样例输出:

19

提示:

折半枚举算法

时间限制: 5000ms
空间限制: 512MB

---