#include <bits/stdc++.h>
using namespace std;
#define int long long
using vi = vector<int>;
using vpii = vector<pair<int,int>>;
#define MOD 1000000007
#define all(arr) arr.begin(), arr.end()
#define take(arr) for(auto &x : arr) cin >> x;
#define print(arr) for(auto &x : arr) cout << x << " "; cout << "\n";
#define out(val) cout<<((val == 1) ? "YES" : "NO")<<endl;
void solve() {
int n,x; cin>>x>>n;
vector<vector<int>> arr(n, vector<int>(3, 0));
for(int i = 0; i<n; ++i){
cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
}
vector<vector<int>> dp(n+1, vector<int>(x+1, 0));
for(int i = 1; i<=n; ++i){
for(int j = 0; j<=x; ++j){
int time = arr[i - 1][2];
for(int k = 0; k<=time; ++k){
if(j >= k*arr[i-1][1]){
dp[i][j] = max(dp[i][j], dp[i-1][j - k*arr[i-1][1]] + k*arr[i-1][0]);
}
}
}
}
cout<<dp[n][x]<<endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
while (t--) {
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... |