#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXXX = 1e4 + 5;
vector<int> dp(MAXXX);
signed main()
{
int n, k;
cin >> k >> n;
vector<int> a(n);
vector<int> b(n);
vector<int> c(n);
for (int i = 0; i < n; i++)
{
cin >> b[i] >> a[i] >> c[i];
}
for (int i = 0; i < MAXXX; i++)
{
dp[i] = 0;
}
if(n == 1)
{
int cnt = k / a[0];
cout << min(c[0], cnt) * b[0];
return 0;
}
for (int i = 0; i < n; i++)
{
for(int j = MAXXX - 1; j >= a[i]; j--)
{
for(int K = 0; K <= c[i]; K++)
{
if(j >= a[i]* K) dp[j] = max(dp[j], dp[j - a[i] * K] + b[i] * K);
}
}
}
int mx = 0;
for(int i = 0; i <= k; i++)
{
mx = max(mx, dp[i]);
}
cout << mx;
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... |