Description

There is a box with capacity $V$, and there are $n$ items. Each item has a volume.

Now choose any number of items from the $n$ items (possibly none) to put into the box, so that the remaining space in the box is minimized. Output this minimum value.

Input Format

The first line contains a single integer $V$, indicating the capacity of the box.

The second line contains a single integer $n$, indicating the total number of items.

The next $n$ lines each contain a positive integer, where the $i$-th line gives the volume of the $i$-th item.

Output Format

Output a single integer in one line, indicating the minimal remaining space in the box.

24
6
8
3
12
7
9
7

0

Hint

Constraints:

• $0 < n \le 30$.
• $1 \le V \le 20000$.

Source: NOIP 2001 Junior, Problem 4.

Translated by ChatGPT 5