Description

选手在 USACO 竞赛中得分越高我们就越高兴。我们要让选手在竞赛中能够得到更多的分数，这需要你的帮忙。竞赛题目可以按题型来分类，每个题型中的题目是无限多的。解决同一类问题的时间和得分都是一样的。你的任务是写一个程序来告诉 USACO 的工作人员，应该从每种题型中选取多少题目，才能让选手在规定的时间内获得最多的分数？

输入包括竞赛总时间 M (1 ≤ M ≤ 10000)（不要担心，你如果不来集训营是不会有这么长的比赛时间的）和题型的总数 N (1 ≤ N ≤ 10000)。接下来的每一行将包括两个整数来描述一种题型：

第一个整数表示这类题目的得分（1 ≤ 得分 ≤ 10000） ，第二个整数表示这类题目的耗时（1 ≤ 耗时≤ 10000） 。 你的程序要帮助我们确定从每类题目中选多少才能在竞赛时间内获得最大的总分。注意每种题型的题目可以不取、只取一道或很多道，请算出选手能够得到的最大分数。

Format

Input

第一行：两个正整数：M 和 N，表示竞赛的总时间和题目类型的数目

第二行到第 N + 1 行：每行两个整数，分别表示每个题型的得分和耗时

Output

第一行：能够得到的最大分数

Samples

300 4
100 60
250 120
120 100
35 20

605

Limitation

从第2种类型中取出4道，再从第4种类型中取出3道。