#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define ll long long
#define vi vector<int>
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define loop(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define dbg(a) cerr << "debug " << #a << ": " << (a) << endl
#define prt(a) cerr << (a) << ' ';
ll mod = 998244353;
int gcd(int a, int b)
{
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
void solve(){
int s, n; cin >> s >> n;
vector<vector<pair<int, int>>> values(s + 1);
for(int i = 0; i < n; i++){
int v, w, k; cin >> v >> w >> k;
values[w].push_back({v, k});
}
for(auto& it: values){
sort(all(it), [](auto& a, auto& b){
return a.first > b.first;
});
}
vector<int> v, w, k;
for(int i = 1; i <= s; i++){
int mamt = s / i;
int cnt = 0;
for(auto it: values[i]){
if(cnt + it.second <= mamt){
w.push_back(i); v.push_back(it.first); k.push_back(it.second);
cnt += it.second;
}
else{
w.push_back(i); v.push_back(it.first); k.push_back(mamt - cnt);
break;
}
}
}
n = v.size();
vector<int> dp(s + 1, -1);
dp[0] = 0;
for(int i = 0; i < n; i++){
for(int j = s; j >= 0; j--){
if(dp[j] == -1) continue;
for(int a = 1; j + a * w[i] <= s && a <= k[i]; a++){
int nw = j + a * w[i];
int np = dp[j] + a * v[i];
dp[nw] = max(dp[nw], np);
}
}
}
// for(auto it: dp) prt(it);
int ans = 0;
for(int i = 0; i < s + 1; i++) ans = max(ans, dp[i]);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// cout.setf(ios::fixed);
// freopen("family.in", "r", stdin);
// freopen("family.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
