#include<bits/stdc++.h>

using namespace std;

const int maxn=30000+10;

int f[maxn];

int zhujianw[maxn],zhujianv[maxn],cijianw[maxn][3],cijianv[maxn][3];

int main(){

    int n,m;

    cin>>n>>m;

    int v,p,q;

for(int i=1;i<=m;i++){

    cin>>v>>p>>q;

    if(!q){

        zhujianw[i]=v,zhujianv[i]=v*p;

    }

    else {

        cijianw[q][0]++;

        cijianw[q][cijianw[q][0]]=v;

        cijianv[q][cijianw[q][0]]=v*p;

    }

}

for(int i=1;i<=m;i++){

    for(int j=n;zhujianw[i]&&j>=zhujianw[i];j--){

        f[j]=max(f[j],f[j-zhujianw[i]]+zhujianv[i]);

        if(j>=zhujianw[i]+cijianw[i][1])

            f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][1]]+zhujianv[i]+cijianv[i][1]);

        if(j>=zhujianw[i]+cijianw[i][2])

    f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][2]]+zhujianv[i]+cijianv[i][2]);

    if(j>=zhujianw[i]+cijianw[i][1]+cijianw[i][2])

        f[j]=max(f[j],f[j-zhujianw[i]-cijianw[i][1]-cijianw[i][2]]+zhujianv[i]+cijianv[i][1]+cijianv[i][2]);

}

}

cout<<f[n]<<endl;

    return 0;

}