noip2005-采药

using namespace std;
const int maxn=1005;
int d[maxn][maxn];
int t[maxn],w[maxn];
int time1,m,ans=-1;
int ()
{
    scanf("%d%d",&time1,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&t[i],&w[i]);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=time1;j++)
        {
            d[i][j]=d[i-1][j];
            if(t[i]<=j)
                d[i][j]=max(d[i][j],d[i-1][j-t[i]]+w[i]);
        }
    for(int i=1;i<=time1;i++) 
        ans=max(ans,d[m][i]);
    printf("%dn",ans);
}