题目背景

完全背包是经典的动态规划问题，在实际生活与算法竞赛中均有广泛应用。

题目描述

设有 $n$ 种物品，每种物品有一个重量及一个价值。每种物品的数量是无限的，同时有一个背包，最大载重量为 $M$。今从 $n$ 种物品中选取若干件（同一种物品可以多次选取），使其重量的和不超过 $M$，而价值的和为最大。

输入格式

第一行两个整数 $M$ 和 $N$，分别表示背包容量和物品种类数。

接下来 $N$ 行，每行两个整数 $W_i, C_i$，分别表示第 $i$ 种物品的重量和价值。

输出格式

输出一行，一个整数，表示最大总价值。

样例

12 4
2 3
3 4
4 5
5 6

15

提示

样例解释

背包容量为 $12$。最优方案：选择 $3$ 个重量为 $4$、价值为 $5$ 的物品，总重量 $4 \times 3 = 12$，总价值 $5 \times 3 = 15$。可以证明这是最大值。

数据范围

• $1 \le M \le 200$
• $1 \le N \le 30$
• $1 \le W_i, C_i \le 100$