#include<cstdio> 
#include<algorithm>
using namespace std;
int w[70],p[70],q[70],f[50000];   
int main()  
{  
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
    int n,m;     
    int l=0;  
    scanf("%d%d",&n,&m);  
    for(int i=1;i<=m;i++)  
    {  
        scanf("%d%d%d",&w[i],&p[i],&q[i]);  
    }  
    for(int i=1;i<=m;i++)  
    {  
        int k1=0;  
        int k2=0;  
        int t1=0;  
        int t2=0;  
        if(q[i]==0)  
        {  
            for(int k=i+1;k<=m;k++)  
                if(q[k]==i)                         
                {  
                    t1=k;  
                    k1=1;  
                    break;  
                }  
                for(int k=t1+1;k<=m;k++)  
                    if(q[k]==i)                         
                    {  
                        t2=k;  
                        k2=1;  
                        break;  
                    }   
                    for(int j=n;j>=w[i];j--)  
                    {         
                        f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]);  
                        f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]);     
                        if((j-w[i]-w[t1])>=0&&k1==1)                           
							f[j]=max(f[j-w[i]-w[t1]]+w[i]*p[i]+w[t1]*p[t1],f[j]);  
                        if((j-w[i]-w[t2])>=0&&k2==1)                                             
                            f[j]=max(f[j-w[i]-w[t2]]+w[i]*p[i]+w[t2]*p[t2],f[j]);  
                        if((j-w[i]-w[t1]-w[t2])>=0&&k1==1&&k2==1)                                             
                            f[j]=max(f[j-w[i]-w[t1]-w[t2]]+w[i]*p[i]+w[t1]*p[t1]+w[t2]*p[t2],f[j]);           
                    }  
        }  
    }  
    printf("%d\n",f[n]);  
    return 0;  
}