#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int maxS = 2e3 + 1;
int N, S;
int f[maxS];
vector<pair<int, int>> item[maxS];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> S >> N;
for(int i = 1, v, w, k; i <= N; ++i){
cin >> v >> w >> k;
item[w].push_back({v, k});
}
for(int w = 1; w <= S; ++w)sort(item[w].begin(), item[w].end(), greater<pair<int, int>>());
// for(int w = 1; w <= S; ++w){
// if(item[w].size()){
// cout << w << "\n";
// for(auto[v, k] : item[w])cout << v << ' ' << k << "\n";
//
// }
// }
for(int s = 1; s <= S; ++s){
for(int j = S; j >= 1; --j){
int W = 0;
int V = 0;
for(auto [v, k] : item[s]){
for(int cnt = 1; cnt <= k; ++cnt){
W += s;
V += v;
if(W <= j) f[j] = max(f[j], f[j - W] + V);
else break;
}
if(W <= j)continue;
else break;
}
}
}
// for(int s = 0; s <= S; ++s){
// cout << f[s] << ' ';
// }cout << '\n';
cout << *max_element(f, f + S + 1);
return 0;
}
