Description

Chen Chen is a talented and gifted child with great potential. His dream is to become the greatest physician in the world. To achieve this, he wants to apprentice under the most esteemed physician in the vicinity. To assess his aptitude, the physician presents him with a challenging problem.

The physician takes him to a cave filled with various herbs and says, "Child, this cave contains different medicinal herbs. Picking each herb requires some time, and each herb has its own value. I will give you a certain amount of time, and within this time, you can gather some herbs.

If you are a clever child, you should be able to maximize the total value of the herbs you collect." If you were Chen Chen, could you accomplish this task?

Input Format

The first line of input contains two integers, T (1 ≤ T ≤ 1000) and M (1 ≤ M ≤ 100). T represents the total available time for gathering herbs, and M represents the number of herbs in the cave.

The following M lines each contain two integers between 1 and 100 (inclusive), representing the time required to gather a particular herb and the value of that herb, respectively.

Output Format

The output consists of a single line containing only one integer, which represents the maximum total value of herbs that can be gathered within the given time.

70 3
71 100
69 1
1 2

3