#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<long long>
#define pb push_back
#define endll "\n"
#define vvll vector<vector<long long>>
const int MOD = 1e9 + 7;
#define rep(i, a , n) for (int i = a; i < (n); i++)
#define nrep(i, n , a) for (int i = n-1; i >= (a); i--)
void solve()
{
ll s, n; cin >> s >> n;
vvll items(n, vll(3));
rep (i, 0, n) {
cin >> items[i][0] >> items[i][1] >> items[i][2];
}
vll dp(s+1, 0);
for (auto item: items) {
vll temp = dp;
ll weight = item[0], value = item[1], count = item[2];
rep (i, weight, s+1){
rep (j, 1, count+1){
if (i - j * weight >= 0) {
temp[i] = max(temp[i], dp[i - j * weight] + j * value);
} else {
break;
}
}
}
dp = move(temp);
}
cout << dp[s] << endll;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt = 1; cin >> tt;
while(tt--) 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... |