Background

Special for beginners, ^_^

Description

有一个箱子容量为v，同时有n个物品，每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

Format

Input

第1行：箱子的容量v（0≤v≤20000）

第2行：物品数n（0≤n≤30）第3~n+2行：每行1个整数，分别表示这n个物品的体积

Output

第1行：1个整数，表示箱子最小的剩余空间

Samples

24   
6   
8    
3
12
7
9
7

0

Limitation

1s, 1024KiB for each test case.