Description

LiYuxiang is a bright child, and his dream is to become the greatest physician in the world. To achieve this, he wants to apprentice under the most respected physician nearby. To assess his aptitude, the physician gave him a challenge. The physician took him to a cave full of herbs and said: "Child, there are different kinds of herbs in this cave. Picking each kind takes some time, and each has its own value. I will give you a period of time. Within this time, you may pick some herbs. If you are clever, you should be able to maximize the total value of the herbs you collect."

If you were LiYuxiang, could you complete this task?

Differences from the original problem:

$1$. Each kind of herb can be picked an unlimited number of times.

$2$. There are many kinds of herbs, and the total picking time can be very long. The master has been waiting for a very long time!

Input Format

The first line contains two integers, representing the total time available for picking herbs $t$ and the number of herb types $m$.

Lines $2$ through $(m + 1)$ each contain two integers. On line $(i + 1)$, the integers $a_i, b_i$ denote the time to pick the $i$-th type of herb and the value of this herb, respectively.

Output Format

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

70 3
71 100
69 1
1 2

140

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $m \le 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq m \leq 10^4$, $1 \leq t \leq 10^7$, and $1 \leq m \times t \leq 10^7$, $1 \leq a_i, b_i \leq 10^4$.

Translated by ChatGPT 5