题解

就是一道完全背包

#include<iostream>
using namespace std;
int dp[1000000],a,b;
int main(){
    int t,m;
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        for(int j=a;j<=t;j++)
            dp[j]=max(dp[j],dp[j-a]+b);
    }
    cout<<dp[t];
    return 0;
}