Minimal Remaining Space in a Box

You are given a box with a capacity of \(V\) and \(n\) items where each item has a volume. Your task is to choose a subset (possibly empty) of the items such that the total volume of the selected items does not exceed \(V\) and the remaining space in the box is minimized.

This can be formulated as finding the subset \(S\) which maximizes \(\sum_{i \in S} v_i\) subject to \(\sum_{i \in S} v_i \leq V\). The minimum remaining space is then given by:

[ \text{Remaining Space} = V - \max\left{\sum_{i \in S} v_i ;\big|; \sum_{i \in S} v_i \le V\right} ]

inputFormat

The first line contains two integers \(V\) (the capacity of the box) and \(n\) (the number of items).

The second line contains \(n\) space-separated integers representing the volumes of the items.

outputFormat

Output a single integer - the minimum remaining space in the box after selecting the optimal subset of items.

sample

50 3
10 20 30

0