题目描述

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

输入格式

第一行两个整数 $W$ 和 $n$。

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

输出格式

一个整数表示答案。

样例

20 5
7 5 4 18 1

19