Start: Jul, 21, 2023 10:00:00
2023暑CSP-J复赛集训DP专题
End: Aug, 21, 2024 04:00:00
Time elapsed:
Time remaining:

装箱问题【动态规划 DP入门】 1253

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:12     AC:8     Score:100


Description

有一个箱子容量为V(正整数,0 ≤ V ≤ 20000),同时有n个物品(0 < n ≤ 30),每个物品有一个体积(正整数)。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

Input

输入有若干行。第一行:一个整数,表示箱子容量V;第二行:一个整数,表示物品个数n;接下来n行,分别表示这n个物品的各自体积。

Output

输出只有一行数据,该行只有一个数,表示最小的箱子剩余空间。

Samples

input:
24 6 8 3 12 7 9 7
output:
0