#include<iostream>
using namespace std;
int N,m,v[60],p[60],q[60];
long long ha=0;
void hahahaha(int n,int i,long long hahaha)
{
if(i>m) return;
if(i==m)
{
if(hahaha>ha) ha=hahaha;
return;
}

if(n>=v[i]&&q[i]>0)
{
if(q[q[i]-1]==-1) hahahaha(n-v[i],i+1,hahaha+v[i]*p[i]);
}

hahahaha(n,i+1,hahaha);
}
void haha(int n,int i,long long hahaha)
{
if(i>m) return;
if(i==m) hahahaha(n,0,hahaha);
if(n>=v[i]&&q[i]==0)
{
q[i]=-1;
haha(n-v[i],i+1,hahaha+v[i]*p[i]);
q[i]=0;
}
haha(n,i+1,hahaha);
}

int main()
{
cin>>N>>m;
for(int i=0;i<m;i++) cin>>v[i]>>p[i]>>q[i];
haha(N,0,0);
cout<<ha<<endl;
return 0;
}

TLE求大神帮改！囧RZ