#include<bits/stdc++.h>
using namespace std;
int w[51000];
int v[51000];
int a[51000];
int f[51000][51000];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>w[i]>>v[i]>>a[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=n;j++) {
            if(w[i]<=j){
                if(a[i]!=1) {
                    int sum=0;
                    for(int k=0;sum+(1<<k)<=a[i];k++){
                        int num=min(a[i]-sum,1<<k);
                        f[i][j]=max(f[i][j],f[i-1][j-num*w[i]]+num*v[i]); 
                        sum+=num;
                    }
                }else{
                    f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
                }
            }
            else f[i][j] = f[i - 1][j];
        }
    }
    cout << f[m][n];
    return 0;
}

代码：