#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 1e5 + 5;
int n , s;
vector<pii> adj[2005];
int dp[2005];
void solve(void){
cin >> s >> n;
for(int i = 1 ; i <= n ; i++) {
int c , w , k; cin >> c >> w >> k;
adj[w].push_back({c , k});
}
for(int i = 1 ; i <= s ; i++){
sort(adj[i].begin() , adj[i].end() , greater<pii>());
for(int j = s ; j >= 0; j--){
int cnt = 0 , sum = 0;
for(int k = 0 ; k < adj[i].size(); k++){
for(int z = 0 ; z < adj[i][k].second ; z++){
cnt++; sum += adj[i][k].first;
if(j < cnt * i) break;
dp[j] = max(dp[j] , dp[j - cnt * i] + sum);
}
}
}
}
int res = 0;
for(int i = 0 ; i <= s; i++) res = max(res , dp[i]);
cout << res;
}
signed main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
solve();
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... |