#include <bits/stdc++.h>
using namespace std;

int main(){
    int t,n;
    while(cin>>t>>n){
        int dp[n+1][t+1];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            int x,y;cin>>x>>y;
            for(int j=0;j<=t;j++){
                if(j>=x)dp[i][j]=max(dp[i-1][j],dp[i-1][j-x]+y);
                else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n][t]<<endl;
    }
}

顺便解释一下01背包问题，希望能帮助到初次了解到这个问题的同学。01背包问题，会使用到一个二维数组，这个二维数组的行表示当前物品，列表示当前背包大小，所有背包问题都基于这个数组求解，背包从0到最大的要求，我们如何得到结果的呢？对于本体，我们需要最大价值，其实对于每个物品，都有几个选项，对于当前背包，该物品可以放入，不可以放入，可以放入的时候，是否放入。假如不可以，自然这个问题就变成了上一个物品当前背包大小的结果了，假如可以，就有两个问题，放入，不放入，放入，这时候，背包变小，为j-x，x为当前物品大小，价值变成当前物品价值，此时问题收缩为j-x大小的时候，前一个物品的放入情况，该情况已经被分析，直接取即可。如此扫描完成数组，即完成了任务。如果同学们问题不好理解，建议到https://www.nowcoder.com/discuss/708721596432674816，看图文版，内有参考的视频版链接