问题 K： 【例86.3】 完全背包问题
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：42
解决：1
题目描述
## 【例86.3】 完全背包问题
时间限制：1000 ms
空间限制：512 MiB
题目类型：传统
### 题目描述
设有 $n$ 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 $M$，今从 $n$ 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于 $M$，而价值的和为最大。
### 输入格式
第一行:两个整数，$M$(背包容量，$M \leq 200$)和 $N$(物品数量，$N \leq 30$) ; 第 $2..N＋1$ 行:每行二个整数 $W_i,C_i$，表示每个物品的重量和价值。
### 输出格式
仅一行，一个数，表示最大总价值。
### 样例
#### 样例输入
```plain
10 4
2 1
3 3
4 5
7 9
```
#### 样例输出
```plain
max=12
```
### 数据范围与提示
### 分类标签
(无)