using namespace std;
#define max( a, b) (a>b? a:b)
int N,m;//总金额和购买物品数
int c[60][4]={-1},w[60][4]={-1},set[60]={0};//商品价值,体积,主件编号
int f[32000]={0};//能够获得的最大价值总和
int main()
{
int i,j,k,v,p,q,t=0;
cin>>N>>m;
for(i=1;i<=m;i++)
{
cin>>v>>p>>q;
if(!q)//如果是主件
{
c[++t][0]=v;
w[t][0]=v*p;
set[i]=t;//记录主件编号
}
//如果是附件
else{
q=set[q];
if(w[q][1]==-1)//编号为q的主件的第一个附件暂时还没找到
{
c[q][1]=c[q][0]+v;
w[q][1]=w[q][0]+v*p;//就把该附件作为编号为q的主件的第一个附件
}
else if(w[q][2]==-1)//编号为q的第二个附件还不存在
{
c[q][2]=c[q][0]+v;
w[q][2]=w[q][0]+v*p;
c[q][3]=c[q][1]+v;//第四种情况直接在带一个附件的基础上加上附件2
w[q][3]=w[q][1]+v*p;
}
}
}
for(i=1;i<=t;i++)
for(k=N;k>=0;k--)
for(j=0;j<4;j++)
if(c[i][j]!=-1&&k-c[i][j]>=0)
{
f[k]=max(f[k],f[k-c[i][j]]+w[i][j]);
}
cout << f[N] << endl;
return 0;
}