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;

}