Description

随着移动支付的发展，越来越多的小偷都开始了转行，作为小偷的祖宗哥布林也开始了灵活就业，现在的大学生全身上下最值钱的就是手里的手机了，但是现在一天24小时，他们巴不得25小时看手机，手机不好偷，那哥布林们就开始思考了，能偷些什么东西呢，显然大学生们的外卖是最合适的目标了，无人看守最容易得手。

于是哥布林首领下令开始窃取人类的外卖，每只哥布林都会有一只大麻袋，大麻袋的体积为 N ，每次他来到宿舍楼下行动的时候可以看到两个外卖的两个属性值 ， 这份外卖的价值 W ，和这份外卖所占的体积为 V ，只要不超过他的袋子的体积他可以装任意份外卖。

请为哥布林计算他使用这个袋子最多能装价值为多少的外卖？

Input Format

第一行输入两个整数 N M (分别表示大麻袋的体积，外卖的份数)

接下来 M 行，每行两个正整数 W , V (分别表示这份外卖的价值和体积)

0<N,V≤1000 0<vi,w≤1000

Output Format

输出一个正整数表示哥布林能装的外卖的金额最大值

10 3
3 3
7 4
5 5​

12​

Hint

样例分析 ：

外卖我们选择 后面的两份 体积为4和体积为5的外卖，这样的价值就是 7 + 5 = 12

Source

DP 数组