#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>> a[2005];
int dp[2005];
int32_t main() {
ios_base::sync_with_stdio(0),cin.tie(0);
int s,n;cin>>s>>n;
for(int i = 0 ; i<=s ; ++i) dp[i] = -1e18;
dp[0] = 0;
for(int i = 0 ; i<n ; ++i) {
int v,w,k;cin>>v>>w>>k;
a[w].push_back({v,k});
}
for(int w = 1 ; w<=s ; ++w) {
sort(a[w].begin(),a[w].end());
int cnt = s/w;
while(!a[w].empty()&&cnt--) {
a[w].back().second--;
int v = a[w].back().first;
for(int j = s ; j>=w ; --j) {
dp[j] = max(dp[j],dp[j-w]+v);
}
while(a[w].back().second == 0) a[w].pop_back();
}
}
int ans = 0;
for(int i = 0 ; i<=s ; ++i) ans = max(ans,dp[i]);
cout << ans;
}
