题目描述

忠实的三体粉丝彬彬在看来动画版之后决定为百合镀金，他有$n$株百合，手上有$m$元，对于第$i$株百合，将它镀金的代价是花费$c_i$元,镀金之后它会变得更美，魅力值为$v_i$。

请问使用彬彬的钱给百合镀金可以使魅力值最高达到多少？

好吧我摊牌了这就是01背包。

输入格式

第一行两个整数，$m$和$n$.

接下来$n$行,每行两个整数$c_i$和$v_i$.

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

60 3
60 80
30 50
30 44

样例输出 #1

94

提示

$1\leq n \leq 100,1\leq m \leq 1000$

$1\leq c_i,v_i \leq 100$