#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
using namespace std;
void quit() {
cout.flush();
exit(0);
}
int main(void){
//freopen("qwer.in", "r", stdin);
//freopen("qwer.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
long long s,n; cin >> s >> n;
vector<vector<pair<long long, long long>>> tmp(2001);
for(long long i = 0; i < n; i++){
long long v,w,k; cin >> v >> w >> k;
tmp[w].emplace_back(v,k);
}
for(long long i = 0; i <= 2000; i++){
sort(tmp[i].begin(), tmp[i].end(), [](pair<int,int> a, pair<int, int> b){
return a.first > b.first;
});
}
vector<long long> dp(2001, -1);
dp[0]=0;
for(long long w = 1; w < 2000; w++){
long long cnt = 0;
long long mx = 2000/w;
for(const auto &item : tmp[w]){
long long upto = min(item.second, mx-cnt);
for(long long i = 0; i < upto; i++){
for(long long j = 2000-w; j >= 0; j--){
if(dp[j] >= 0){
dp[j+w]=max(dp[j+w],dp[j]+item.first);
}
}
}
cnt += item.second;
if(cnt > mx){
break;
}
}
}
long long ans = 0;
for(long long i = 0; i <= s; i++){
ans = max(ans, dp[i]);
}
cout << ans << "\n";
quit();
}
