题目描述
设有n种物品,每种物品有一个价值,但每种物品的数量是无限的,同时有一个背包,最大承载量为m,今从n种物品中选取若干件,(同一种物品可以多次选取)使其重量的和小于等于m,而且装入背包物品价值的和最大。
输入描述
共N+1行
第一行:两个整数:M(背包容量M<=200)和N(物品数量,N<=30);
第二行至第N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值(wi,ci<=1000)。
输出描述
一个数,表示最大的价值;
样例输入
10 4
2 1
3 3
4 5
7 9
样例输出
12
提示