Description

Chenchen is a talented and gifted child whose dream is to become the greatest physician in the world. To achieve this, he wants to learn from the most prestigious physician in the area. To test his aptitude, the physician gave him a challenge. The physician took him to a cave full of herbs and said: "Child, there are different herbs in this cave. Each herb takes some time to collect and has its own value. I will give you a certain amount of time, during which you can collect some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you collect."
If you were Chenchen, could you complete this task?

Input Format

The first line contains two integers $T$ ($1 ≤ T ≤ 1000$) and $M$ ($1 ≤ M ≤ 100$), where $T$ represents the total time available for collecting herbs, and $M$ represents the number of herbs in the cave. The next $M$ lines each contain two integers between $1$ and $100$ (inclusive), representing the time needed to collect a herb and its value.

Output Format

Output a single line containing one integer, representing the maximum total value of herbs that can be collected within the given time.

Sample

70 3
71 100
69 1
1 2

3