Start 2024-04-06 14:20:00

20240406 背包问题一(maoyu)

End 2024-04-13 00:00:00
Contest is over.
Now 2026-11-19 00:33:23

E. 简单背包问题2

Description

有一个背包容量为v,同时有n个物品,每个物品有一个体积。要求从n个物品中,任取若干个装入包内,使背包的剩余空间最少。

Input

第一行为一个整数v(正整数,0\le v\le20000),表示背包容量,第二行为一个整数n(0\le n\le30),表示有n个物品,接下来n行,分别表示这n个物品的各自体积(正整数)。

Output

只有一个整数,表示背包的最少剩余空间。

Examples

Input

24
6
8
3
12
7
9
7

Output

0

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit