#include<bits/stdc++.h>
using namespace std;
struct thi
{
    int v[3];
    int p[3];
    int cnt;//计数，存到第几个附件
}th[65];
int n,m;
long long dp[32005];
int main()
{
	int a,b,c;
    //shuru
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>a>>b>>c;
        //第i件物品的价格、重要度以及它对应的的主件
        if(c!=0)
        {
        	th[c].v[++th[c].cnt]=a;
        	th[c].p[th[c].cnt]=b;
		}
		else
		{
			th[i].v[0]=a;
        	th[i].p[0]=b;
		}
	}
    //chuli
    for(int i=1;i<=m;i++)
    for(int j=n;j>=th[i].v[0];j-=10)
    {
        if(dp[j-th[i].v[0]]+th[i].v[0]*th[i].p[0]>dp[j])
        {
            dp[j]=dp[j-th[i].v[0]]+th[i].v[0]*th[i].p[0];
            	if(th[i].v[0]+th[i].v[1]<=j&&dp[j-th[i].v[0]-th[i].v[1]]+th[i].v[1]*th[i].p[1]+th[i].v[0]*th[i].p[0]>dp[j])
            		dp[j]=dp[j-th[i].v[0]-th[i].v[1]]+th[i].v[1]*th[i].p[1]+th[i].v[0]*th[i].p[0];
            	if(th[i].v[0]+th[i].v[2]<=j&&dp[j-th[i].v[0]-th[i].v[2]]+th[i].v[2]*th[i].p[2]+th[i].v[0]*th[i].p[0]>dp[j])
					dp[j]=dp[j-th[i].v[0]-th[i].v[2]]+th[i].v[2]*th[i].p[2]+th[i].v[0]*th[i].p[0];
				if(th[i].v[0]+th[i].v[1]+th[i].v[2]<=j&&dp[j-th[i].v[1]-th[i].v[2]]+th[i].v[1]*th[i].p[1]+th[i].v[2]*th[i].p[2]+th[i].v[0]*th[i].p[0]>dp[j])
					dp[j]=dp[j-th[i].v[0]-th[i].v[1]-th[i].v[2]]+th[i].v[1]*th[i].p[1]+th[i].v[2]*th[i].p[2]+th[i].v[0]*th[i].p[0];
        }
        else dp[j]=dp[j]; 
    }
    //shuchu
    cout<<dp[n];
    return 0;
}