#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<vector<int>>> dp;
int s,n;
vector<int> value, weight, copies;
int find_ans(int level, int maxi, int can_take){
if(level == n){
return 0;
}
if(dp[level][maxi][can_take] != -1) return dp[level][maxi][can_take];
int ans = 0;
// take eleme //
if(can_take > 0 && maxi>=weight[level]) ans = max(ans, value[level] + find_ans(level, maxi-weight[level], can_take-1));
// not take //
ans = max(ans, find_ans(level+1, maxi, copies[level+1]));
return dp[level][maxi][can_take] = ans;
}
void solve(){
cin>>s>>n;
value.resize(n+1);
copies.resize(n+1);
weight.resize(n+1);
int maxi = 0;
for(int i=0;i<n;i++){
cin>>value[i]>>weight[i]>>copies[i];
maxi = max(maxi, copies[i]);
}
dp.assign(n, vector<vector<int>>(s+1, vector<int>(maxi+1, -1)));
cout<<find_ans(0, s, copies[0])<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n_test = 1;
// cin>>n_test;
while(n_test--){
solve();
}
}
