aaaaaagf @ 2023-08-07 15:05:58
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
int n,m;
LL f[70],fw[40000][3],fv[40000][3];//fw代表附件的钱,fv代表附件的价值
struct{
LL a,b;
}sz[70];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++){
int q,w,e;
cin>>q>>w>>e;
if(!e){
sz[i].a=q;
sz[i].b=w*q;
}
else{
fw[e][0]++;//记录附件个数
fw[e][fw[e][0]]=q;
fv[e][fw[e][0]]=q*w;
}
}
for(int i=1;i<=m;i++){
for(int j=n;j>=sz[i].a;j--){
f[j]=max(f[j],f[j-sz[i].a]+sz[i].b);//只选主件或不选
if(j>=sz[i].a+fw[i][1]) f[j]=max(f[j],f[j-sz[i].a-fw[i][1]]+sz[i].b+fv[i][1]);//只选主件和附件1或不选
if(j>=sz[i].a+fw[i][2]) f[j]=max(f[j],f[j-sz[i].a-fw[i][2]]+sz[i].b+fv[i][2]);//只选主件和附件2或不选
if(j>=sz[i].a+fw[i][1]+fw[i][2]) f[j]=max(f[j],f[j-sz[i].a-fw[i][2]-fw[i][1]]+sz[i].b+fv[i][2]+fv[i][1]);//都选或者都不选
}
}
cout<<f[n];
return 0;
}