302002 - 0/1背包问题

有一个最多能用m公斤的背包,有n件物品,它们的重量分别是W_1,W_2,…,W_n,它们的价值分别为C_1,C_2,…,C_n。若每件物品只有一件,问能装入的最大总价值。

输入

第一行为两整数m和n(1\le m,n\le1 000),以下n行中,每行两个整数W_i,C_i,分别代表第i件物品的重量和价值。

输出

输出一整数,即最大价值。

样例

输入

8 3
2 3
5 4
5 5

输出

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