Description

Chen Chen is a gifted child whose dream is to become the greatest physician in the world. To achieve this, he wants to apprentice under the most prestigious physician in the vicinity. To assess his aptitude, the physician presents him with a challenge. The physician takes him to a cave filled with herbs and says, "Child, this cave contains various herbs. Picking each herb takes some time, and each herb has its own value. I will give you a certain amount of time, during which 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), separated by a space. T represents the total time available for herb gathering, 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 required to pick a particular herb and the value of that herb, respectively.

Output Format

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

```input1 70 3 71 100 69 1 1 2 ``` ```output1 3 ``` ## Hint

【Data Range】

For 30% of the data, M ≤ 10;
For all data, M ≤ 100.

Source

NOIP2005-J3