题目描述

上古，黄帝垂衣裳而天下治，华夏渐入文明之范畴。《白虎通·衣裳》云：“圣人所以制衣服何？以为絺绤蔽形，表德劝善，别尊卑也。”《风俗通义·愆礼》云：“衣者，隐也；裳者，障也；所以隐形自障闭也。巾，所以饰首；衣，所以蔽形。”典籍文献屡次表衣冠之大乃民生之首，衣冠之美可比华章；则买布裁衣于生活必不可少。

现在店有数种布匹，并标有价钱与精致的程度（每种布匹只有数量 1）。现有一定数目的钱，求用这些钱能买布的精致程度之和的最大值。

输入格式

第一行有两个由空格分开的数据 $m$，$n$，其中 $m$ 是钱的数目（ $m \le 5000$），$n$ 是布的匹数（$n \le 100$）。

接着有 $n$ 行，每行有两个数据，分别表示每中布匹的价钱和精致程序。

输出格式

在输入数据下的所有能买布的精致程度之和的最大值。

样例

50 6
2 6
3 7
1 2
3 3
4 9
2 3

30

10 5
2 6
2 3
6 5
5 4
4 6

15