Gathering Herbs

Problem Background

Special for beginners, ^_^

Problem Description

Chenchen is a gifted child whose dream is to become the world's greatest physician. To this end, he wants to apprentice himself to the most respected physician nearby. To test his aptitude, the physician gives him a hard problem: he takes Chenchen to a cave full of medicinal herbs and says, "Child, this cave has various herbs; gathering each one takes some time, and each has its own value. I will give you a span of time, during which you may gather some herbs. If you are a clever child, you should be able to maximise the total value of the herbs you gather."

If you were Chenchen, could you complete this task?

Input Format

The first line of input contains two 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 gathering herbs, and $M$ is the number of herbs in the cave. The following $M$ lines each contain two integers between $1$ and $100$ (inclusive), representing the time needed to gather a certain herb and its value.

Output Format

A single line containing a single integer: the maximum total value of herbs that can be gathered within the given time.

Sample Input 1

70 3
71 100
69 1
1 2

Sample Output 1

3

Hint

This is a dynamic-programming problem:

1. First divide into stages — here we naturally take "picking the $i$-th herb" as the stage boundary.

2. Then describe the state. Since the problem asks for the maximum total value gathered, and considering the stages together with the constraints (2 dimensions), we can use $f[i][j]$ to mean: choosing among the first $i$ herbs with a time limit of at most $j$, the maximum total value that can be gathered.

3. The crucial step is the state-transition equation. Consider two cases, as in a dfs: the $i$-th herb can either be picked or not.

   • If we pick the $i$-th herb, then in $f[i][j]$ we must reserve the last $t[i]$ units of time for it, and the time limit for the first $i-1$ herbs becomes $j-t[i]$. The maximum value then is $f[i-1][j-t[i]] + v[i]$, where $t[i]$ is the time to gather the $i$-th herb and $v[i]$ is its value.
   • If we do not pick the $i$-th herb, the maximum value obtainable from the first $i$ herbs is $f[i-1][j]$, i.e. all time is left for the first $i-1$ herbs.

   We take the maximum of these two options and assign it to $f[i][j]$, giving $$f[i][j] = \max(f[i-1][j], f[i-1][j-t[i]]+v[i])$$.