#498. 【例9.12】完全背包问题(商品体积有负数)

【例9.12】完全背包问题(商品体积有负数)

题目描述

设有nn种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为MM,今从nn种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于MM,而价值的和为最大。

输入格式

第一行:两个整数,MM(背包容量,M10000M≤10000)和NN(物品数量,N10000N≤10000); 第2..N+12..N+1行:每行二个整数Wi,CiW_i,C_i,表示每个物品的重量和价值。

输出格式

仅一行,一个数,表示最大总价值。

样例

输入样例

10 4
2 1
3 3
4 5
7 9

样例输出

max=12

数据范围与提示

30Wi,Ci30-30 \leq W_i,C_i \leq 30

对于100%的测试数据, 0M300,0W3000 \leq M \leq 300, 0 \leq W \leq 300