问题 J： 【例86.2】 01背包问题
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：84
解决：2
题目描述
## 【例86.2】 01背包问题
时间限制：1000 ms
空间限制：512 MiB
题目类型：传统
### 题目描述
一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $W_1，W_2，...,W_n$.它们的价值分别为 $C_1,C_2,... ,C_n$，求旅行者能获得最大总价值。
### 输入格式
第一行:两个整数，$M$(背包容量，$M \leq 200$)和$N$(物品数量，$N \leq 30$) ; 第 $2..N＋1$ 行:每行二个整数 $W，C$，表示每个物品的重量和价值。
### 输出格式
仅一行，一个数，表示最大总价值。
### 样例
#### 样例输入
```plain
10 4
2 1
3 3
4 5
7 9
```
#### 样例输出
``` plain
12
```
### 数据范围与提示
### 分类标签
(无)