using namespace std;
int p1[50000];//最大值
struct data
{
int shu;
int per;
int fu;
};
data k[70];
int main()
{
int a=0;//总钱数
int b=0;//物品数
int c=0;
int d=0;
int f=0;
int q1=0;//标志位
int q2=0;//标志位
cin>>a;
cin>>b;
for(int i=1;i<=b;i++)
{
cin>>k[i].shu;//价钱
cin>>k[i].per;//重要度
cin>>k[i].fu;//是否是附属品
}
for(int i=1;i<=b;i++)
{
c=0;
d=0;
q1=0;
q2=0;
if(k[i].fu==0)
{
for(f=i+1;f<=b;f++)
if(k[f].fu==i)
{
c=f;
q1=1;
break;//找出第一件附属品
}
for(f=c+1;f<=b;f++)
if(k[f].fu==i)
{
d=f;
q2=1;
break;//找出第二件附属品
}
for(int j=a;j>=k[i].shu;j--)
{
if(p1[j-k[i].shu]+k[i].shu*k[i].per>p1[j])
p1[j]=p1[j-k[i].shu]+k[i].shu*k[i].per;//只有主件
if((j-k[i].shu-k[c].shu)>=0&&q1==1)
{
if(p1[j-k[i].shu-k[c].shu]+k[i].shu*k[i].per+k[c].shu*k[c].per>p1[j])
p1[j]=p1[j-k[i].shu-k[c].shu]+k[i].shu*k[i].per+k[c].shu*k[c].per;//主件和附件1
}
if((j-k[i].shu-k[d].shu)>=0&&q2==1)
{
if(p1[j-k[i].shu-k[d].shu]+k[i].shu*k[i].per+k[d].shu*k[d].per>p1[j])
p1[j]=p1[j-k[i].shu-k[d].shu]+k[i].shu*k[i].per+k[d].shu*k[d].per;//主件和附件2
}
if((j-k[i].shu-k[d].shu-k[c].shu)>=0&&q1==1&&q2==1)//主件和附件1和附件2
{
if(p1[j-k[i].shu-k[d].shu-k[c].shu]+k[i].shu*k[i].per+k[d].shu*k[d].per+k[c].shu*k[c].per>p1[j])
p1[j]=p1[j-k[i].shu-k[d].shu]+k[i].shu*k[i].per+k[d].shu*k[d].per+k[c].shu*k[c].per;
}
}
}
}
cout<<p1[a];
//while(1);
return 0;
}