#include<bits/stdc++.h>
using namespace std;
int n,m,f[40000],g[40000];
struct obj{
    int price,value,team;
}a[100];
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&a[i].price,&a[i].value,&a[i].team),a[i].value*=a[i].price;
    for(int i=1;i<=m;i++)
        if(!a[i].team)
        {
            for(int j=1;j<a[i].price;j++)
                g[j]=0;
            for(int j=a[i].price;j<=n;j++)
                g[j]=f[j-a[i].price]+a[i].value;
            for(int j=1;j<=m;j++)
          	  if(a[j].team==i)
            		for(int k=n;k>=a[i].price+a[j].price;k--)
                        g[k]=max(g[k],g[k-a[j].price]+a[j].value);
            for(int j=a[i].price;j<=n;j++)
                f[j]=max(f[j],g[j]);
        }
    cout<<f[n]<<endl;
    return 0;
}