#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[31], c[31], p[31];
int f[201];

/*
10 3
2  1  0
3  3  1
4  5  4
*/

int main(){
    scanf("%d%d",&m,&n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d",&w[i],&c[i],&p[i]);
    for (int i = 1; i <= n; i++)
        if (p[i] == 0)  {                                   //完全背包
            for (int j = w[i]; j <= m; j++)
                f[j] = max(f[j], f[j-w[i]]+c[i]);
        }
        else {
            for (int j = 1; j <= p[i]; j++)           //01背包和多重背包
                for (int k = m; k >= w[i]; k--)
                    f[k] = max(f[k],f[k-w[i]]+c[i]);
        }
        
    printf("%d",f[m]); 
    return 0;
}