#include<bits/stdc++.h>
using namespace std;
int main() {
int s , n;
cin >> s >> n;
vector<vector<pair<int,int>>> weight_to_info(s + 1);
for(int i = 0;i < n; i++){
int v , w , k;
cin >> v >> w >> k;
weight_to_info[w].push_back({v , k});
}
vector<pair<int,int>> cantake;
for(int i = 1;i <= s; i++){
sort(weight_to_info[i].rbegin(), weight_to_info[i].rend());
int cur = 0;
for(auto &x : weight_to_info[i]){
while(cur < s && x.second > 0){
cur++;
cantake.push_back({x.first, i});
x.second--;
}
}
}
//knapsack:
vector<vector<int>> dp(cantake.size() + 1 , vector<int> (s + 1, 0));
dp[0][0] = 0;
for(int i = 1;i <= cantake.size() ;i++) {
for(int j = 0;j <= s; j++) {
dp[i][j] = dp[i - 1][j];
int w = cantake[i - 1].second;
int cost = cantake[i - 1].first;
if( j - w >= 0){
dp[i][j] =max(dp[i][j] , dp[i - 1][j - w] + cost);
}
}
}
cout << dp[cantake.size()][s] << endl;
}
