#include<bits/stdc++.h>
using namespace std;
int Nm,m;
int upq,p,q;
int main_w[35];
int main_c[35];
int att_main[35];
int att_w[35][3];
int att_c[35][3];
int f[32020];
int main()
{
    cin>>Nm>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&upq,&p,&q);
        if(q==0)
        {
            main_w[i]=upq;
            main_c[i]=upq*p;
        }else
        {
            att_main[q]++;
            att_w[q][att_main[q]]=upq;
            att_c[q][att_main[q]]=upq*p;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(main_w[i]!=0)
        {
            for(int j=Nm;j>=main_w[i];j--)
            {
                f[j]=max(f[j],f[j-main_w[i]]+main_c[i]);
                if(j>=main_w[i]+att_w[i][1])
                {
                    f[j]=max(f[j],f[j-main_w[i]-att_w[i][1]]+main_c[i]+att_c[i][1]);
                }
                if(j>=main_w[i]+att_w[i][2])
                {
                    f[j]=max(f[j],f[j-main_w[i]-att_w[i][2]]+main_c[i]+att_c[i][2]);
                }
                if(j>=main_w[i]+att_w[i][1]+att_w[i][2])
                {
                    f[j]=max(f[j],f[j-main_w[i]-att_w[i][1]-att_w[i][2]]+main_c[i]+att_c[i][1]+att_c[i][2]);
                }
            }
        }
    }
    printf("%d",f[Nm]);
    return 0;

}```