#include <bits/stdc++.h>
using namespace std;
const int S = 2000, N = 1e5;
int arr[S+1];
int main() {
int s, n;
cin >> s >> n;
vector<pair<int, int>> weights[s+1];
for (int x = 0; x < n; x ++){
int v, w, k;
cin >> v >> w >> k;
k = min(k, s/w);
weights[w].push_back({v, k});
}
for (int x = 1; x <= s; x ++){
sort(weights[x].begin(), weights[x].end());
for (int c = 0; c < s/x; c ++){
if (weights[x].empty()){
break;
}
int v = weights[x].back().first;
for (int i = s-x; i >= 0; i --){
arr[i+x] = max(arr[i+x], arr[i]+v);
}
for (int i = 1; i <= s; i ++){
arr[i] = max(arr[i], arr[i-1]);
}
weights[x][weights[x].size()-1].second --;
if (weights[x].back().second == 0){
weights[x].pop_back();
}
}
}
cout << arr[s] << endl;
return 0;
}
