#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n,m;
cin >> n >> m;
vector<pair<long long, long long>> pq;
long long dp[n + 1];
for(long long i = 0; i <= n; i++){
dp[i] = 0;
}
for(long long i = 0; i < m; i++){
long long a,b,c;
cin >> a >> b >> c;
pq.push_back({a, b});
while(c > 1){
pq.push_back({a, b});
c--;
}
long long u = pq.size();
// for(long long k = n; k >= a; k--){
// dp[k] = max(dp[k], dp[k - a] + b);
// }
}
long long y = pq.size();
long long ans1 = 0;
if(n == 1){
for(long long i = 0; i < y; i++){
long long ans1 = max(ans1, pq[i].ff);
}
cout << ans1;
return 0;
}
else{
for(long long i = 0; i < y; i++){
for(long long k = n; k >= pq[i].ss; k--){
dp[k] = max(dp[k], dp[k - pq[i].ss] + pq[i].ff);
}
}
long long ans = 0;
for(long long i = 0; i <= n; i++){
ans = max(ans, dp[i]);
}
cout << ans;
}
// while (t--) {
// long long k;
// long long x;
// cin >> k >> x;
// vector<long long> s2s = solve(k, x);
// cout << s2s.size() << "\n";
// for (long long i = 0; i < s2s.size(); i++) {
// if (i > 0) cout << " ";
// cout << s2s[i];
// }
// cout << "\n";
// }
// return 0;
}
