#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
using namespace std;
const int maxn = 2005;
int n;
int s;
struct node
{
int v, w, k;
};
node a[100005];
bool cmp(node a, node b)
{
return a.v > b.v;
}
int used[maxn];
int dp[maxn];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen(".inp" , "r" , stdin);
// freopen(".out" , "w" , stdout);
cin >> s >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].v >> a[i].w >> a[i].k;
}
sort(a + 1, a + n + 1, cmp);
//3 1
//2 1 3
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int sl = 1; sl <= a[i].k; sl++){
if(used[a[i].w] * a[i].w > s) break;
for(int sum = s; sum >= a[i].w; sum--){
dp[sum] = max(dp[sum], dp[sum - a[i].w] + a[i].v);
}
used[a[i].w]++;
}
}
int res = 0;
for(int i = 0; i <= s; i++){
// cout << dp[i] << " ";
res = max(res, dp[i]);
}
// cout << "\n";
cout << res << "\n";
}
