minkite @ 2018-10-04 21:22:15
//c++
#include<bits/stdc++.h>
using namespace std;
#define N 20000
int f[N][2000];
int zy[N][3];
int qs[N][3];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
if(z!=0)
{
zy[i][0]=y;
qs[i][0]=x;
}
else
if(qs[z][1]!=0)
{
zy[i][1]=y;
qs[i][1]=x;
}
else
{
zy[i][2]=y;
qs[i][2]=x;
}
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(j-qs[i][0]>=0)
{
f[i][j]=max(f[i-1][j],f[i-1][j-qs[i][0]]+qs[i][0]*zy[i][0]);
if(j-qs[i][1]-qs[i][0]>=0)
f[i][j]=max(f[i-1][j],f[i-1][j-qs[i][0]-qs[i][1]]+qs[i][0]*zy[i][0]+qs[i][1]*zy[i][1]);
if(j-qs[i][2]-qs[i][0]>=0)
f[i][j]=max(f[i-1][j],f[i-1][j-qs[i][0]-qs[i][2]]+qs[i][0]*zy[i][0]+zy[i][2]*qs[i][2]);
if(j-qs[i][2]-qs[i][1]-qs[i][0]>=0)
f[i][j]=max(f[i-1][j],f[i-1][j-qs[i][0]-qs[i][1]]+qs[i][0]*zy[i][0]+zy[i][1]*qs[i][1]-zy[i][2]*qs[i][2]);
}
else
f[i][j]=f[i-1][j];
}
cout<<f[m][n];
return 0;
}