猫史档案馆

题面：

 

作为惩罚，小G被遣去帮别人送礼物。

 

某人有N个礼物，每个礼物都有一个很大的重量G[i]，但是小G的力气也异常的大，他一次可以搬动重量和小于W的任意多个物品。小G希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

 

输入：

 

第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i]。

 

输出：

 

仅一行一个整数，表示小G在他的力气范围内一次性能搬动的最大重量。

 

样例输入：

 

20 5
1
2
15
12
2    

样例输出

19


数据范围：

对于20%的数据N≤26

对于100%的数据N≤45,W≤2147483喵7,G[i]≤2147483喵7

贪心假的，dfs超时，dp空间不够，考虑蓝书上说是双向搜索，有没有人能给一下代码，万分感谢！