P1048 [NOIP 2005 Junior] Herb Picking

Chenchen is a gifted child whose dream is to become the greatest physician in the world. To this end, he wants to apprentice with the most respected physician nearby. To assess his aptitude, the physician gave him a challenge. He took him to a cave full of herbs and said, “Child, there are different kinds of herbs in this cave. Picking each herb takes some time, and each has its own value. I will give you a period of time. During this time, you can pick some herbs. If you are clever, you should be able to maximize the total value of the herbs you pick.” If you were Chenchen, could you complete this task?

The first line contains $2$ integers $T$ ($1 \le T \le 1000$) and $M$ ($1 \le M \le 100$), separated by a space. $T$ is the total time available for picking, and $M$ is the number of herbs in the cave. Each of the next $M$ lines contains two integers between $1$ and $100$ inclusive, representing the time to pick a herb and the value of that herb.

Output the maximum total value of herbs that can be picked within the given time.

**Constraints** - For $30\%$ of the testdata, $M \le 10$. - For all testdata, $M \le 100$. **Source** NOIP 2005 Junior, Problem 3. Translated by ChatGPT 5