#P1004. 板板缺货 救救胡桃

板板缺货 救救胡桃

说明

胡桃是往生堂的堂主,但是因为棺材缺货,胡桃必须去寻找做棺材的原料,可是胡桃忙着陪Mrnaoketong去打怪,请你给他想想办法,让她如何在规定的时间内搞到最多的木头来做棺材

输入格式

第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)T表示胡桃总共能用来找木头的时间,M表示树的数量

接下来的M行每行包括两个在1到100之间的的整数,分别用来表示砍倒某棵树的时间和这棵树能得到多少做棺材的材料。

输出格式

输出在规定的时间内可以获得的最多的木头的数量

样例

70 3
71 100
69 1
1 2
3

提示

01背包板子题