Dooler最大的爱好就是睡觉,可是睡觉多了自然做梦的次数也就多了,他被各种奇怪的梦缠绕着~ 

最近,Dooler因为整天想着请MM吃饭,可苦于囊中羞涩，生活在拮据当中。于是这天他梦入神机，竟然来到了一间藏宝室，各种各样的财宝让Dooler眼花缭乱，头晕目炫，于是乎聪明的Dooler竟然不知道如何取舍了...可怜的他发现身上只有一个口袋，是不可能装得下所有的这些财宝的（财宝不可分割）。而且为了表现得低调一些，他是不准备用手抱着把财宝带回去的，所以如何用口袋装回最大价值的财宝这个问题，让Dooler感到脑袋不够用了。所以，为了不让Dooler带着遗憾睡醒，只有靠更聪明的你的头脑了，我们准备把他能用口袋装回的最大价值送入到他的梦里去，让他自己去解决如何选择的问题。 

输入包含多个测试实例，每个实例的第一行是两个整数v和n(v,n < = 100)，分别表示Dooler口袋的容量和宝贝的种类，接着的n行每行包含2个整数pi和mi(0 < pi,mi < 10)，分别表示某种宝贝的价值和对应的体积，v为0的时候结束

对于每个测试实例，请输出ZY最多能取回多少价值的宝贝，每个实例的输出占一行。