#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll s,n;
cin >> s >> n;
vector<pair<ll,ll>> dp(s+1,{-1,0});
vector<vector<ll>> vec(n);
for(int i = 0;i < n;i++){
ll v,w,k;
cin >> v >> w >> k;
vec[i] = {v,w,k};
}
for(int i = 0;i <= s;i++){
ll v = vec[0][0];
ll w = vec[0][1];
ll k = vec[0][2];
if((i % w == 0) && ((i / w) <= k)){
dp[i] = {v * (i / w),(i / w)};
}
}
/*for(int i = 0;i <= s;i++){
cout << "dp[0][" << i << "] = {" << dp[i].first << "," << dp[i].second << "}" << endl;
}*/
for(int i = 1;i < n;i++){
vector<pair<ll,ll>> temp(s+1,{-1,0});
ll v = vec[i][0];
ll w = vec[i][1];
ll k = vec[i][2];
for(int j = 0;j <= s;j++){
ll tot_val = -1;
ll count = 0;
if(dp[j].first != -1) tot_val = max(tot_val,dp[j].first);
/*if((j - w >= 0) && (temp[j-w].first != -1) && (temp[j - w].second < k)){
if(tot_val < (v + temp[j-w].first)){
tot_val = v + temp[j-w].first;
count = temp[j-w].second + 1;
}
}*/
if(k*w < s){
for(int p = 1;p <= k;p++){
if(j - p*w < 0) break;
if((j - p*w >= 0) && (dp[j - p*w].first != -1)){
if(tot_val < (dp[j - p*w].first + p*v)){
tot_val = dp[j - p*w].first + p*v;
count = p;
}
}
}
}
else{
tot_val = max(tot_val,temp[j-w].first + v);
count = INT_MAX;
}
temp[j] = {tot_val,count};
//cout << "dp[" << i << "][" << j << "] = {" << temp[j].first << "," << temp[j].second << "}" << endl;
}
dp = temp;
}
ll answer = 0;
for(int i = 1;i <= s;i++){
answer = max(answer,dp[i].first);
}
cout << answer << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
