#include<iostream>
#include<cstdio>
#define maxn 100
using namespace std;
int ma(int x,int y)
{
    return x>y?x:y;
}
int n,m;
int v[maxn][4],p[maxn][4],q[maxn]; 
int a[100000];//千万别和我一样杀币开小了 
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1,x,y,z;i<=n;++i){
        scanf("%d%d%d",&x,&y,&z);
        if(z==0)//如果是主件的话 
        {
            v[i][1]=x;p[i][1]=y;q[i]=0;//主件1 
        }
        else//附件存入a[z][2/3]中 
        {
            if(v[z][2]==0)//附件2是不是存入了
            {v[z][2]=x;p[z][2]=y;q[i]=1;}//附件1
            else
            {v[z][3]=x;p[z][3]=y;q[i]=1;}//附件2
        }
    }
    for(int i=1;i<=n;++i)
    {
        if(q[i]==0)//是不是主件，附件就不考虑了 
        for(int j=m;j>=v[i][1];j--)    
        {
            if(j>=v[i][1])//买主件 
            a[j]=max(a[j],a[j-v[i][1]]+p[i][1]*v[i][1]);
            if(j>=v[i][1]+v[i][2])//主件+附件1 
            a[j]=max(a[j],a[j-v[i][1]-v[i][2]]+p[i][1]*v[i][1]+p[i][2]*v[i][2]);
            if(j>=v[i][1]+v[i][3])//主件+附件2 
            a[j]=max(a[j],a[j-v[i][1]-v[i][3]]+p[i][1]*v[i][1]+p[i][3]*v[i][3]); 
            if(j>=v[i][1]+v[i][2]+v[i][3])//主件+附件1+附件2 
            a[j]=max(a[j],a[j-v[i][1]-v[i][2]-v[i][3]]+v[i][1]*p[i][1]+p[i][2]*v[i][2]+p[i][3]*v[i][3]);
        }
        //if真多，打完都怀疑人生了 
    } 
    cout<<a[m];//输出结果就好了 
    return 0;
}