#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
输入一个NNN和一个mmm,NNN表示现有的钱,mmm表示有mmm件物品,接着输入每件物品的价格、重要度、是否附属等信息
对于主件物品可以直接买,对于附件物品需要先购买主件才能购买附件,主件有0-2个附件
所有的价格,及金额都是10的整数倍
在不超过金额NNN元的情况下,使购买的每件物品的价格与重要度乘积的和最大,求这个最大值
方法一:动态规划
具体做法:
因为每个主件只有0-2个附件,且附件必须在买了主件的前提下,才能买,因此我们可以用3∗m的数组保存价格和重要度与价格的乘积,第一维就是主件,第二三维是主件后面跟的附件,只有主件下标的元素才有值,附件下标的数组元素就都是0。且因为金钱和价格都是10的整数倍,我们可以对其除10,缩小使用的时间和空间。
然后我们用动态规划来解决这个问题,设dp[i][j]dp[i][j]dp[i][j]表示遍历了i个主件物品及其附件,我们有j元钱最多能买多少乘积和,容易看出来dp[m][N]dp[m][N]dp[m][N]就是我们要求的答案。
初始状态:0件物品,或是0元,那肯定都是0; 转移的过程中,我们优先考虑遍历的主件物品,如果当前jjj大于等于这个主件物品的价格,我们可以考虑加入买它或者不买他,分别计算买或者不买的最大值,如果要买的需要前一次还剩余j−pricej-pricej−price的钱才能买,于是我们有:
dp[i][j]=max(dp[i−1][j],dp[i−1][j−price[i][0]]+multisum[i][0])dp[i][j]=max(dp[i-1][j], dp[i-1][j-price[i][0]]+multisum[i][0])dp[i][j]=max(dp[i−1][j],dp[i−1][j−price[i][0]]+multisum[i][0]),遍历所有的iii和jjj将dp数组填满就行了,这是最基础的01背包问题。
但是这题不一样,这题还要考虑附件,因此我们后续还要考虑jjj是否足够买这个下标下的主件加第一个附件,这个下标下的主件加第二个附件,这个下标下的主件加两个附件三种请况,每次都是寻找上一轮剩余的钱足够买的乘积和加上这一轮得到的乘积和,取最大值就可以了。公式类似上面主件部分。比如主件+第一个附件的公式:
dp[i][j]=max(dp[i−1][j−price[i][0]−price[i][1]]+multisum[i][0]+multisum[i][1],dp[i][j]) dp[i][j] = max(dp[i-1][j - price[i][0] - price[i][1]] + multisum[i][0] + multisum[i][1], dp[i][j])dp[i][j]=max(dp[i−1][j−price[i][0]−price[i][1]]+multisum[i][0]+multisum[i][1],dp[i][j])
遍历dp数组,填满得到dp[m][N]dp[m][N]dp[m][N]就可以了。
*/
int main(){
int N, m;
cin >> N >> m;
N /= 10; //所有价格及金钱都是10倍数
vector<vector<int> > price(m + 1, vector<int>(3, 0)); //记录价格及附件价格
vector<vector<int> > multi_sum(m + 1, vector<int>(3, 0)); //记录重要度*价格
vector<vector<int> > dp(m + 1, vector<int>(N + 1, 0)); //dp数组
for(int i = 1; i <= m; i++){ //遍历输入,将所有价格及乘积信息录入数组
int v, p, q;
cin >> v >> p >> q; //输入价格、重要度、附属信息
v /= 10; //所有价格及金钱都是10倍数
p *= v; //重要度乘上价格
if(q == 0){ //主件
price[i][0] = v;
multi_sum[i][0] = p;
}else{ //附件
if(price[q][1] == 0){ //第一个附件
price[q][1] = v;
multi_sum[q][1] = p;
}else{ //第二个附件
price[q][2] = v;
multi_sum[q][2] = p;
}
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= N; j++){
if(j >= price[i][0]) //可以买这个的主件
dp[i][j] = max(dp[i - 1][j - price[i][0]] + multi_sum[i][0], dp[i - 1][j]); //选择买这个与不买这个的最大值
else
dp[i][j] = dp[i - 1][j];
if(j >= price[i][0] + price[i][1]) //可以买主件 + 第一个附件
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1]] + multi_sum[i][0] + multi_sum[i][1], dp[i][j]);
if(j >= price[i][0] + price[i][2]) //可以买主件 + 第二个附件
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][2]] + multi_sum[i][0] + multi_sum[i][2], dp[i][j]);
if(j >= price[i][0] + price[i][1] + price[i][2]) //可以买主件 + 两个附件
dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1] - price[i][2]] + multi_sum[i][0] + multi_sum[i][1] + multi_sum[i][2], dp[i][j]);
}
}
cout << dp[m][N] * 10 << endl; //输出要乘回10倍
return 0;
}