#include<bits/stdc++.h>
using namespace std;
#define TASK "task"
const int mxN = 2e3 + 7;
const int inf = 1e9 + 67;
int n;
int s;
long long dp[mxN][mxN];
vector<pair<int,int>>groups[mxN];
void solve(void) {
cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v , w , k;
cin >> v >> w >> k;
groups[w].push_back(make_pair(v , k));
}
for (int i = 0; i <= s; i++)
sort(groups[i].begin() , groups[i].end() , greater<pair<int,int>>());
for (int i = 1; i <= s; i++) {
for (int j = 0; j <= s; j++)
dp[i][j] = dp[i - 1][j];
if(!groups[i].size()) continue;
// với cân nặng i thì chỉ có thể lấy nhiều nhất S / i cái
for (int j = s; j >= 0; j--) {
int w = 0;
long long v = 0;
for (auto it : groups[i]) {
int k = it.second;
while(k > 0 && w <= j) {
w += i;
v += it.first;
--k;
if(j >= w) dp[i][j] = max(dp[i][j] , dp[i - 1][j - w] + v);
}
}
}
}
long long ans = -inf;
for (int i = 0; i <= s; i++)
for (int j = 0; j <= s; j++)
ans = max(ans , dp[i][j]);
cout << ans;
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp","r",stdin);
//freopen(TASK".out","w",stdout);
int tc = 1;
//cin >> tc;
while(tc--) solve();
return 0;
}
