题目描述

Bessie 和她的诸多姐妹一样，因为从 Farmer YDS 的草地吃了太多美味的草而长出了太多赘肉。所以 Farmer YDS 将她置于一个极其严格的节食计划之中。

她每天不能吃超过 $H$ 公斤的干草。Bessie 只能吃一整捆干草；当她开始吃一捆干草之后就再也停不下来了。

现在有 $N$ 捆干草可以给她当作晚餐。每捆干草只能被吃一次，即使列表中相同的重量可能出现多次，也表示不同的干草捆。

给定每捆干草的重量 $S_i$，请在不超过节食限制的前提下，求 Bessie 最多可以吃多少公斤的干草。

输入格式

第一行输入两个整数 $H,N$，分别表示每天最多能吃的干草重量和干草捆数。

接下来 $N$ 行，每行一个整数 $S_i$，表示第 $i$ 捆干草的重量。

输出格式

输出一个整数，表示 Bessie 在限制范围内最多可以吃多少公斤的干草。

样例

56 4
15
19
20
21

56

数据范围

$5 \le H \le 45000$，$1 \le N \le 500$，$1 \le S_i \le H$。

来源

动态规划 / 01 背包