#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct ab{int w,v,k;}a[1010]; 
bool cmp(ab x,ab y){return x.w<y.w;}
void dfs(int step,int sum,int wt,int b)
{
    if(wt>m) return;
    if(b!=a[step-1].k&&step==1) return;
    if(step>n)
    {
        ans=max(ans,sum);
        return;
    }
    dfs(step+1,sum,wt,b);
    dfs(step+1,sum+a[step].v,wt+a[step].w,a[step].k);
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].v>>a[i].k;
    sort(a+1,a+n+1,cmp);
    dfs(1,0,0,0);
    cout<<ans;
    return 0;
}