题目描述

达达帮翰翰给女生送礼物，翰翰一共准备了 $N$ 个礼物，其中第 $i$ 个礼物的重量是 $G[i]$。

达达的力气很大，他一次可以搬动重量之和不超过 $W$ 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 $W$ 和 $N$。

以后 $N$ 行，每行一个非负整数表示 $G[i]$。

输出格式

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

样例

输入样例：

20 5
7
5
4
18
1

输出样例：

19

样例解释

$W = 20, N = 5$
礼物重量：7, 5, 4, 18, 1

可以搬动重量不超过 20 的组合：
选择 7 + 5 + 4 + 1 = 17
选择 18 + 1 = 19
选择 7 + 5 + 4 = 16
……
最大重量是 19（18 + 1），不超过 20。

数据范围

• $1 \le N \le 46$
• $1 \le W \le 2^{31} - 1$
• $0 \le G[i] \le 2^{31} - 1$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB