5649 - 提高:双向DFS:运输

通过次数

25

提交次数

60

时间限制 : 1 秒
内存限制 : 128 MB

目前有n堆垃圾,每堆垃圾的重量为Gi,运输车每次可以运输重量之和不超过W的任意多堆垃圾,你希望一次运掉尽可能中的一些垃圾,请计算下能一次运输最大重量是多少?

输入

第一行两个整数,分别是代表W和N; 以后N行,每行一个正整数表示Gi

输出

一个整数,表示一次能运掉最大重量是多少

样例

输入

20 5
7
5
4
18
1

输出

19

提示

1<=N<=46;

1<=W,GI<=2^31-1