1666. 桃饱

桃桃是一个憨憨又可爱(●'◡'●)的孩子,她最开心的事就是吃好吃的,“吃好吃,长胖胖!我,桃桃,要成为全世界最胖的桃桃!耶!”。 ( •̀ ω •́ )y 可可爱爱没有脑袋的她踩着兴奋的小碎步去到了饭堂,打算参加饭堂门口的光盘行动。“饭盘吃光光,奖品抽光光。”作为一个平时就不剩饭的好孩子,桃桃对于参加这次活动十分期待。一到饭堂,桃桃的眼中闪出了星星般耀眼的光芒“青瓜炒火腿!紫菜蛋花汤!番茄炒蛋!土豆丝!……”,虽然对于每一道喜欢的菜品都毫无抵抗,但是为了勤俭节约,吃光饭盘参加活动,她必须保证自己吃到最满意的菜的同时吃完所有菜。桃桃在内心嘀咕了一下,为每个菜品打了分数,而且每个菜的量都不一样,所以必须好好计划。 如果你是桃桃,你能让自己吃饱的同时还能吃到最满意吗?(在有限饭量内达到最大总分数)

输入

第一行有2个整数*C ( 1 ≤ C ≤ 1000 )* 和*N ( 1 ≤ N ≤ 100 )*,用一个空格隔开,C代表桃桃的饭量,N代表桃桃喜欢的菜品的数目。 接下来的*N*行,每行有两个整数,都大于等于1且小于等于100,分别表示这道菜的量和这道菜在桃桃内心的分数。

输出

输出在规定饭量内可以吃到的最大总分数

样例

标准输入 复制文本
90 3
99 100
89 80
1 20
标准输出 复制文本
100

来源

ERENMASON

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 3
通过 3