#1300. 装箱问题

装箱问题

题目描述

有一个箱子容量为V\red{V}(正整数,0<=V<=20000\red{0<=V<=20000}),同时有n\red{n}个物品(0n<=30\red{0<n<=30}),每个物品有一个体积(正整数)。

要求n\red{n}个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入格式

第一行为一个整数,表示箱子容量;

第二行为一个整数,表示有n\red{n}个物品;

接下来n行,每行一个整数表示这n\red{n}个物品的各自体积。

输出格式

一个整数,表示箱子剩余空间。

样例

输入样例

24
6
8
3
12
7
9
7

输出样例

0