#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define int long long
const int mxS=2e3;
ll dp[mxS+1];
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int s, n; cin>>s>>n;
vector<array<ll, 3>> v(n);
for(int i=0; i<n; i++) {
cin>>v[i][0]>>v[i][1]>>v[i][2];//v, w, k
}
fill(dp, dp+mxS+1, -1e18);
dp[0]=0;
ll ans=0;
for(int i=0; i<n; i++) {
ll use=v[i][2];
for(int j=1; use>0; j*=2) {
ll x=min(use, j)*v[i][1];
ll val=1ll*min(use, j)*v[i][0];
for(int k=s; k>=x; k--) {
dp[k]=max(dp[k], dp[k-x]+val);
ans=max(ans, dp[k]);
}
use-=min(use, j);
}
}
cout<<ans;
return 0;
}
# | 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... |