1277 : 做梦!

时间限制:1 Sec 内存限制:128 MiB
提交:144 答案正确:73

提交 状态 讨论区

题目描述

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

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

输入

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

输出

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

样例输入

复制
5 3
3 2
3 3
7 4
0

样例输出

复制
7

提示


			

来源