桃桃是一个憨憨又可爱(●'◡'●)的孩子,她最开心的事就是吃好吃的,“吃好吃,长胖胖!我,桃桃,要成为全世界最胖的桃桃!耶!”。
( •̀ ω •́ )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