记录编号	47575	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]采药	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-11-02 08:41:27	内存使用	5.86 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 + 10;
int n, c, v[N], w[N], f[N][N];
int main() {
    freopen("medic.in", "r", stdin);
    freopen("medic.out", "w", stdout);
    scanf("%d %d", &c, &n);
    /*
    for(int i=1; i<=n; i++)
        scanf("%d %d", v+i, w+i);
    */ /*
    for(int i=n; i>=1; i--)
        for(int j=0; j<=c; j++) {
            f[i][j] = (i == n) ? 0 : f[i+1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i+1][j - v[i]] + w[i]);
        } printf("%d\n", f[1][c]);
    */ /*
    for(int i=1; i<=n; i++)
        for(int j=0; j<=c; j++) {
            f[i][j] = (i == 1) ? 0 : f[i-1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
        } printf("%d\n", f[n][c]);
    */ /*
    int a, b;
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &a, &b);
        for(int j=0; j<=c; j++) {
            f[i][j] = (i == 1) ? 0 : f[i-1][j];
            if(j >= a)
                f[i][j] = max(f[i][j], f[i-1][j - a] + b);
        }
    } printf("%d\n", f[n][c]);
    */
    int a, b, d[N] = {0};
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &a, &b);
        for(int j=c; j>=0; j--)
            if(j >= a)
                d[j] = max(d[j], d[j - a] + b);
    } printf("%d\n", d[c]);
    return 0;
}