3930 - 01背包

有一个体积为V的背包, 有n种物品,告诉你每种物品的体积与价值

现在求这个背包最多能装入多少价值的物品
 

输入

第一行输入两个整数$V,n$, ($1 \le V \le 1000, 1 \le n \le 100$)

接下来$n$行每行输入两个整数$a_i,b_i$ ($1 \le a_i, b_i \le 100$)

输出

输出一行包含一个整数,表示最多能装入背包的价值

样例

输入

70 3
71 100
69 1
1 2

输出

3

提示

对于30%的数据,n <= 10;
 

对于全部的数据,n <= 100。

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