The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.

We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.

The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.

Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).

Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.

PROGRAM NAME: inflate

INPUT FORMAT

SAMPLE INPUT (file inflate.in)

300 4
100 60
250 120
120 100
35 20

OUTPUT FORMAT

SAMPLE OUTPUT (file inflate.out)

605

題意：
給出比賽最大時間M及比賽題目類型數目N。每種題目類型里可以有無數個題目。接下來N行，給出每種題目類型里一個題目的分數
和限定時間。要求在滿足總時間M的情況下，能使得分數最多的題目安排。

代碼如下：

/*
LANG: C
TASK:inflate
*/
#include<stdio.h>
#define nmax 10001
int score[nmax];
int main()
{
    freopen("inflate.in", "r", stdin);
    freopen("inflate.out", "w", stdout);
    int n, m, i, j, s, t;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        score[i] = 0;
    }
    for (i = 0; i < m; i++)//[i, j]表示前i+1種類型的題中，時間為j得到的最大分數 
    {
        scanf("%d%d", &s, &t);
        for (j = t; j <= n; j++)//因為對每種類型。取一題就需要t時間。所以可以從t開始。 
        {
            if (score[j] < score[j - t] + s)
            {
                score[j] = score[j - t] + s;
            }
        }
    }
    printf("%d\n", score[n]);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}