#include <iostream>
using namespace std;
/*
状态表示f[i,j]：
    集合：从前i组选且总钱数不大于j的选法所获得的价值总和
    属性：最大值
状态计算：
    f[i-1,j]不选第i组的物品
    f[i-1,j-v[i,k]]+w[i,k]选第i组的某些物品
        有以下情况：
            只购买主件
                任何情况下都可以
            购买主件和一个附件
                有至少一个附件可以
            购买主件和两个附件
                必须要有两个附件
       于是，可以把每组物品组合成若干01背包的物品，将整个问题转化成01背包问题
*/
int n, m;
int v[65][65], w[65][65], s[65], wh[65];
int f[32000];

int main()
{
    cin >> n >> m;
    int a, b, c;
    int k = 0;
    // wh用于从行号映射到组号
    for(int i=1; i<=m; i++)
    {
        cin >> a >> b >> c;
        if(c == 0){
            k++;
            v[k][0] = a;
            w[k][0] = b*a;
            wh[i] = k;
        } else {
            s[wh[c]]++;
            v[wh[c]][s[wh[c]]] = a;
            w[wh[c]][s[wh[c]]] = b*a;
        }
    }

    // i是组号
    for(int i=1; i<=k; i++)
        for(int j=n; j>=v[i][0]; j--)
        {
            if(j >= v[i][0])
                f[j] = max(f[j], f[j-v[i][0]]+w[i][0]);
            if(s[i] == 1)
            {
                // 只能购买一个附件
                if(j >= v[i][0]+v[i][1])
                    f[j] = max(f[j], f[j-v[i][0]-v[i][1]]+w[i][0]+w[i][1]);
            }
            else if(s[i] == 2)
            {
                // 购买其中一个附件
                if(j >= v[i][0]+v[i][1])
                    f[j] = max(f[j], f[j-v[i][0]-v[i][1]]+w[i][0]+w[i][1]);
                if(j >= v[i][0]+v[i][2])
                    f[j] = max(f[j], f[j-v[i][0]-v[i][2]]+w[i][0]+w[i][2]);
                //  购买全部两个附件
                if(j >= v[i][0]+v[i][1]+v[i][2])
                    f[j] = max(f[j], f[j-v[i][0]-v[i][1]-v[i][2]]+w[i][0]+w[i][1]+w[i][2]);
            }
        }

    cout << f[n];
}