题目描述

设有一个背包可以放入的物品重量为 $S$，现有 $n$ 件物品，重量分别是 $w_1,w_2,w_3,...,w_n$。问能否从这 $n$ 件物品中选择若干件放入背包中，使得放入的重量之和正好为 $S$。如果有满足条件的选择，则此背包有解，否则此背包问题无解。

输入格式

第一行为物品重量 $S$， 第二行为物品数量 $n$，第三行为 $n$ 件物品的重量的序列。