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