#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 2003;
int dp[MAXN];
vector<vector<int>> items(2003);
int main(){
for(int i =0; i < MAXN; i++)dp[i]=0;
int s,n; cin >> s >> n;
for(int i = 0; i < n; i++){
int v,w,k; cin >> v >> w >> k;
for(int i = 0; i < s/w; i++){
if(i >= k)break;
items[w].push_back(v);
}
}
int maxmax = -1;
for(int i =0; i <= s; i++)sort(items[i].begin(),items[i].end(),greater<int>());
for(int i = 1; i <= s; i++){ // item ind
int smol = min((int)items[i].size(),s/i);
for(int j = 0; j < smol; j++){ //num of items taken
for(int k = s; k >= i; k--){
dp[k] = max(dp[k], dp[k-i]+items[i][j]);
}
}
}
for(int i =0; i < MAXN; i++)maxmax = max(maxmax,dp[i]);
cout << maxmax << endl;
}
