P1049 [NOIP 2001 Junior] Box Packing Problem

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.

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 a single integer in one line, indicating the minimal remaining space in the box.

Constraints: - $0 < n \le 30$. - $1 \le V \le 20000$. Source: NOIP 2001 Junior, Problem 4. Translated by ChatGPT 5