#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
const int N =32010, M = 60;
int f[N];
typedef pair<int,int> PII;
vector<PII> servant[M];
PII master[M];
int m,n;

int main()
{
    cin>>m>>n;
    for(int i = 1; i <= n; i ++)
    {
        int v,w,q;
        cin>>v>>w>>q;
        if(!q)
            master[i] = {v, v*w};


        else
            servant[q].push_back({v, v*w});
    }

    for(int i = 1; i <= n; i ++)
        for(int u = m; u >= 0; u --)
            for(int j = 0; j < 1<<servant[i].size(); j ++) //如果有两个附件，那么有四种组合方式，j的含义就是组合方式
            {
                int v = master[i].first, w = master[i].second;
                for(int k = 0; k < servant[i].size(); k ++) //如果有两个附件，移位两次。
                //比如当j为00时，第一件物品和第二件物品经过位运算都为0，即都不取
                //当j为01时，第一件物品取，第二件物品不取
                {   
                    if(j >> k & 1)
                    {
                        v = v + servant[i][k].first;
                        w = w + servant[i][k].second;
                    }
                }

                if(u >= v) f[u] = max(f[u], f[u-v] + w);
            }

    cout<<f[m];

}