#include <bits/stdc++.h>
using namespace std;
int main(){
int s, n;
cin >> s >> n;
vector<int> val(n), wt(n), num(n);
for(int i = 0; i < n; i++){
cin >> val[i] >> wt[i] >> num[i];
}
vector<pair<int, int>> how;
for(int i = 0; i < n; i++){
for(int j = 0; j < min(s / wt[i], num[i]); j++){
how.push_back({val[i], wt[i]});
}
}
int sz = how.size();
int dp[sz + 1][s + 1];
for(int i = 0; i <= sz; i++){
for(int j = 0; j <= s; j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}
}
}
for(int i = 1; i <= sz; i++){
for(int j = 1; j <= s; j++){
if(how[i - 1].second <= j){
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - how[i - 1].second] + how[i - 1].first);
} else{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[sz][s] << '\n';
}
