#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <map>
#define ll long long int
const ll mod=1000000009;
using namespace std;
/*
? Did I test edge cases? (Empty, min/max, 1-element, same elements, etc.)
? Did I reread the full prompt to recheck constraints?
? Does my code handle ties, negatives, zeroes, or duplicates?
? Am I brute-forcing something unnecessarily?
? Am I assuming things not in the problem?
*/
int main(int argc, char** argv) {
ios_base::sync_with_stdio(false);
int s,n;
cin>>s>>n;
vector<ll> a,weight;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
for(int j=0;j<z;j++)
{
a.push_back(x);
weight.push_back(y);
}
}
ll dp[s+1][a.size()];
dp[0][0]=0;
for(int i=0;i<=s;i++)
{
for(int j=0;j<a.size();j++)
{
if(i)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=0;
if(j)
dp[i][j]=max(dp[i][j-1],dp[i][j]);
if(i>=weight[j])
{
if(j)
dp[i][j]=max(dp[i][j],dp[i-weight[j]][j-1]+a[j]);
else
dp[i][j]=max(dp[i][j],a[j]);
}
}
}
cout<<dp[s][a.size()-1];
}
