E09【模板】背包DP 完全背包

/*
完全背包：每种宝石可以取多个（只要时间够）
程序很简单：只要j从小到大枚举即可，此时计算f[j]时用到了f[jj](jj<j)，而f[jj]已经在外层第i次循环中计算过了（也就是有了第i颗宝石的影响）
所以f[j]的计算用到了包含第i颗宝石影响的小规模状态，f[j]就相当于有多次第i颗宝石影响，相当于第i颗宝石可以取多次。 
*/
#include<bits/stdc++.h>
using namespace std;
int t[110],m[110];
int f[1100];
int main()
{
    int T,n;scanf("%d%d",&T,&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&m[i]);
    memset(f,0,sizeof(f)); 
    for(int i=1;i<=n;i++)
    {
       for(int j=t[i];j<=T;j++)
       {
            f[j]=max(f[j],f[j-t[i]]+m[i]);
       }
    }
    printf("%d\n",f[T]);
    return 0;
}