#P3047. 奥奥的购物袋

奥奥的购物袋

Description

奥奥去超市购物,他有一只容量为V的购物袋,同时他买了n件物品,已知每件物品的体积v[i]。蒜头君想知道,挑选哪些物品放入购物袋中,可以使袋子剩余的空间最小。

Input Format

第一行输入一个整数V(1≤V≤20,000),表示购物袋的容量。

第二行输入一个整数n(1≤n≤30),表示蒜头君购买的n件物品。

接下来输入n行,每行输入一个整vi​(1≤vi​≤10,000),表示第i件物品的体积。

Output Format

输出一行,输出一个整数,表示购物袋最小的剩余空间。

20
5
7
5
7
3
7
1

Source

信奥星OJ http://127.0.0.1