#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, s;
cin >> s >> n;
vector<vector<pl>> nums (s+1);
for (ll i = 0; i < n; i++){
ll v, w, k;
cin >> v >> w >> k;
nums[w].push_back({v, k});
}
vector<pl> prvky;
for (ll i = 1; i <= s; i++){
ll pocet = 0;
ll limit = s/i+1;
sort(nums[i].begin(), nums[i].end());
reverse(nums[i].begin(), nums[i].end());
for (ll j = 0; j < nums[i].size(); j++){
for (ll k = 0; k < nums[i][j].second; k++){
prvky.push_back({nums[i][j].first, i});
pocet++;
if (pocet >= limit){
break;
}
}
if (pocet >= limit){
break;
}
}
}
vl dp(s+1, 0);
for (ll i = 0; i < prvky.size(); i++){
ll p = prvky[i].first;
ll v = prvky[i].second;
for (ll j = s; j >= v; j--){
dp[j] = max(dp[j], dp[j-v] + p);
}
}
ll maximum = 0;
for (ll i = 0; i < s+1; i++){
maximum = max(maximum, dp[i]);
}
cout << maximum <<"\n";
return 0;
}
