说明

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

输入格式

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

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

输出格式

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

样例

70 3
71 100
69 1
1 2

3

提示

01背包板子题