#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> triad;
#define int long long
#define INF 1e9
int s,n,val,weight,occ,ans;
vector<int> dp;
vector<vector<tuple<int,int>>> items;
bool update(int value, int w,int att){
if(att*w > s){
return false;
}
for(int i = dp.size()-w-1; i >= 0; i--){
dp[i + w] = max(dp[i+w], dp[i] + value);
}
return true;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> n;
dp.resize(s+1);
items.resize(s+1);
//int mod = 1e9+7;
dp[0] = 0;
for(int i = 0; i < n; i++){
cin >> val >> weight >> occ;
if(weight > s){
continue;
}
items[weight].push_back({val,occ});
}
for(int i = 0; i <= s; i++){
sort(items[i].begin(), items[i].end());
for(int j = items[i].size() - 1; j >= 0; j--){
val = get<0>(items[i][j]);
occ = get<1>(items[i][j]);
bool help = true;
int att = 1;
while(occ-- && help){
help = update(val,i,att);
att++;
}
if(!help){
break;
}
}
}
ans = dp[s];
cout << ans;
return 0;
}
