#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cstdarg>
using namespace std;
int dp[61][32001];
int bel[61];
int w[61];
int cost[61];
vector<int> fujian[61];
int rank[61];
int main()
{ 
    freopen("budget.in", "r", stdin);
    freopen("budget.out", "w", stdout);
    int N, n;
    scanf("%d %d", &N, &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", cost+i, w+i, bel+i);
        if(bel[i])   //是附件
            fujian[bel[i]].push_back(i);
    }
    int p = 1;
    for(int i = 1; i <= n; i++) //记录主件
        if(!bel[i])rank[p++] = i;
    for(int i = 1; i < p; i++)  //枚举主件
    {
        for(int j = 0; j <= N; j++)  //剩余RMB
        {
            int tmp = 0;
            for(int k = 0; k < (1<<fujian[rank[i]].size()); k++)  //子集枚举
            {
                int s = cost[rank[i]];                    //占的总花费
                int sss = w[rank[i]]*cost[rank[i]];       //得到的总目标值
                for(int l = 0; l < fujian[rank[i]].size(); l++)
                {
                    if((1<<l)&k)   //第l个附件选上
                    {
                        s += cost[fujian[rank[i]][l]];
                        sss += cost[fujian[rank[i]][l]]*w[fujian[rank[i]][l]];
                    }
                }
                if(j >= s)  //能装下
                {
                    tmp = max(tmp, dp[i-1][j-s]+sss);
                }
            }
            dp[i][j] = max(tmp, dp[i-1][j]);
            if(j < cost[rank[i]])
                dp[i][j] = dp[i-1][j];
        }
    }
    printf("%d\n", dp[p-1][N]); 
    return 0;
}