#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii=pair<ll,ll>;
const int N=2020;
int s,n,dp[N];
void calc(int v,int w){
for(int i=s;i>=w;i--){
dp[i]=max(dp[i],dp[i-w]+v);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>s>>n;
for(int i=0;i<n;i++){
int v,w,k,now=1,kk;cin>>v>>w>>k;
kk=k;
while(now<=kk&&kk>0&&ll(now*w)<=s){
calc(v*now,w*now);
kk-=now;
now<<=1;
}
if(kk>0&&kk*w<=s) calc(v*kk,kk*w);
}
cout<<dp[s];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |