1442 - 部分背包

一个旅行者有一个最多能装M公斤的背包,现在有n件物品,它们的重量分别是wi,它们的价值分别是vi元/公斤,求旅行者能获得最大总价值。

输入

第1行:两个整数,M背包容量(M<=1000)和N物品数量(N<=30);

第2至N+1行:每行两个整数wi,vi,表示每个物品的重量和价值。

输出

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

样例

输入

100 3
40 2
50 3
70 3

输出

300

来源

HC

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题