问题 A: 01背包

问题 A: 01背包

时间限制: 1 Sec  内存限制: 128 MB
提交: 182  解决: 136
[提交] [状态] [讨论版] [命题人:]

题目描述

一个旅行者有一个最多能装m公斤物品的背包,现在有n件物品,它们的重量分别是w1,w2,…,wn,它们的价值分别为c1,c2,…,cn。若每一种物品只有一件,求旅行者能获得的最大总价值

输入

第一行:两个整数,m(背包容量,m<=200)和n(物品数量,n<=30)。

第二~n+1行:每行两个整数wi,ci,表示每个物品的重量和价值


输出

一个数据,表示最大总价值




样例输入

10 4
2 1
3 3
4 5
7 9

样例输出

12

[提交][状态]