#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 5010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
struct things
{
int v,w,k;
}a[maxn];
int n,s;
namespace sub1
{
void solve()
{
cout << min(s / a[1].w,a[1].k) * a[1].v;
}
}
namespace sub2
{
int dp[N];
void solve()
{
fo(i,1,n)
{
fod(j,s,1) if(j >= a[i].w)
dp[j] = max(dp[j],dp[j - a[i].w] + a[i].v);
}
cout << dp[s];
}
}
namespace sub3
{
int dp[maxn];
vector<things> arr;
void solve()
{
fo(i,1,n)
{
fo(j,1,min(s / a[i].w,a[i].k)) arr.push_back({a[i].v,a[i].w,1});
}
for(auto [v,w,k] : arr)
{
fod(j,s,1) if(j >= w)
dp[j] = max(dp[j],dp[j - w] + v);
}
cout << dp[s];
}
}
namespace full
{
vii adj[N];
int dp[N][N];
vi v;
void solve()
{
fo(i,1,n)
{
if(a[i].w < s) adj[a[i].w].pb(a[i].v,a[i].k),v.pb(a[i].w);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
fo(i,0,n) fo(j,0,s) dp[i][j] = -inf;
dp[0][0] = 0;
for(int i = 0 ; i < v.size() ; i++)
{
int it = v[i];
sort(adj[it].begin(),adj[it].end(),[](pii a,pii b)
{
return a.fi > b.fi;
});
fo(sum,it,s)
{
dp[i + 1][sum] = max(dp[i + 1][sum],dp[i - 1][sum]);
int profit = 0,pos = 0,used = 0,tot = 0;
while(tot + it < sum and pos < adj[it].size())
{
tot += it;
used++;
profit += adj[it][pos].fi;
dp[i + 1][sum] = max(dp[i + 1][sum],dp[i][sum - tot] + profit);
if(used == adj[it][pos].se)
{
used = 0;
pos++;
}
}
}
}
cout << dp[n][s];
}
}
main()
{
#define name "TASK"
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> s >> n;
fo(i,1,n) cin >> a[i].v >> a[i].w >> a[i].k;
if(n == 1) sub1::solve();
else full::solve();
// else if(n <= 100) sub3::solve();
}
