说明

某天菜某人在外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