#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnoff(x,y) ((x)^(1<<y))
using namespace std;
int s, n;
struct shen
{
int v, w, k;
} a[100005];
int cnt[2005];
int dp[2005];
bool cmp(shen x, shen y)
{
return x.v < y.v;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> s >> n;
for (long i = 1; i <= n; i++){
cin >> a[i].v >> a[i].w >> a[i].k;
}
sort(a+1, a+n+1, cmp);
int ans = 0;
for (long i = 1; i <= n; i++){
int v = a[i].v, w = a[i].w, k = a[i].k;
for (long j = 1; j <= k; j++){
if (cnt[w]*w > s) break;
for (long z = s; z >= w; z--){
dp[z] = max(dp[z], dp[z - w] + v);
ans = max(ans, dp[z]);
}
cnt[w]++;
}
}
cout << ans;
}
