#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int s, n;
vector<pair<int,int>> W[2005];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> n;
for(int i = 1; i <= n; i++){
int v, w, k;
cin >> v >> w >> k;
if(w <= s && k > 0)
W[w].push_back({v, k});
}
vector<ll> dp(s+1, 0);
// duyệt theo trọng lượng
for(int w = 1; w <= s; w++){
if(W[w].empty()) continue;
// lấy các value, tối đa S / w món
vector<int> vals;
for(auto &[v, k] : W[w]){
int take = min(k, s / w);
while(take--) vals.push_back(v);
}
if(vals.empty()) continue;
sort(vals.begin(), vals.end(), greater<int>());
int m = vals.size();
vector<ll> pre(m+1, 0);
for(int i = 0; i < m; i++)
pre[i+1] = pre[i] + vals[i];
vector<ll> new_dp = dp;
// group knapsack
for(int t = 1; t <= m; t++){
int weight = t * w;
if(weight > s) break;
for(int x = weight; x <= s; x++){
new_dp[x] = max(new_dp[x], dp[x - weight] + pre[t]);
}
}
dp.swap(new_dp);
}
cout << *max_element(dp.begin(), dp.end());
return 0;
}
