#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
inline void solve(){
int s, n;
cin>>s>>n;
vector<pair<int,int>> a[s+1];
for(int i=0; i<n; i++){
int v, w, k;
cin>>v>>w>>k;
a[w].push_back({v, k});
}
vector<int> ldp(s+1, 0), dp(s+1);
for(int w=1, i=0; w<=s; w++){
sort(a[w].rbegin(), a[w].rend());
int c = 0;
for(auto [v, k] : a[w]){
for(; k > 0 and c < s/w; i++, c++, k--){
for(int j=0; j<=s; j++){
dp[j] = ldp[j];
if(j-w >= 0) dp[j] = max(dp[j], ldp[j-w] + v);
}
swap(ldp, dp);
}
}
}
cout<<ldp[s];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
