#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int s,w,v;
int dp[2][N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(0);
    int i,j,k,m,n,p,maxn=-1e9;
    cin>>i>>j;
    for(k=1;k<=j;++k)
    {
        cin>>s>>w>>v;
        int x=k&1;
        for(m=0;m<=i;++m)
        {
            for(p=0;p<=s&&p*v<=m;++p)
            {
                dp[x][m]=max(dp[x^1][m],dp[x^1][m-p*v]+p*w);
                 
            }   
        }
 
    }
    cout<<dp[j&1][i];
    return 0;
 
}