#P1008. 练习板子 完全背包

练习板子 完全背包

说明

某天菜某人在外zhuangai,途径一家民宅,发现小偷偷家,你神奇的发现小偷带了一个哆啦a梦的口袋,想把目标家的东西全部带走,菜某人作为一个热心的公民立马拨打了报警电话,警察来的很快,迅速的将小偷逮捕。但是菜某人在某个时候降小偷的神奇口袋“顺”走了,但因为能力有限只能开启v大小的空间。回到家中,发现家里有n种东西,每样东西都占用w的空间,你决定模仿一下小偷用这个口袋来装一下家里价值x的各种东西。

输入格式

第一行输入你能打开的口袋空间大小v和物品种类个数n;(0<=v<=1000,0<=n<=100);

接下来n行分别输入物品的大小w和其价值;

每一种物品都可以重复使用

输出格式

输出结果得到一个最大价值

样例

50 4
8 8
4 4
3 3
2 2
50