#include <bits/stdc++.h>
using namespace std;
#define xi first
#define yi second
#define endl '\n'
#define MAX (int)2007
typedef long long ll;
typedef long double ld;
typedef long long ll;
const long long md = (ll) 1e9 + 7;
long long gcd(long long a, long long b) {
if (b == 0)return a;
return (a % b) ? gcd(b, a % b) : b;
}
int mst_sig_bit(long long num) {
int cnt = -1;
while (num)num = num >> (ll) 1, cnt++;
return cnt;
}
long long fst_pow(long long a, long long N) {
if (N == 0) return 1;
long long R = fst_pow(a, N / 2);
if (N % 2) return ((R * R) % md * a) % md;
else return (R * R) % md;
}
vector<pair<ll, ll>>tmp[2007];
ll cnt[2007][2007];
ll dp[2007];
int hlp[2007];
int mx[2007];
int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(0);
int s, n;
cin>>s>>n;
for(int x=0;x<n;++x){
int v, w, k;
cin>>v>>w>>k;
tmp[w].push_back({v, k});
}
for(int x=1;x<=s;x++){
if(tmp[x].empty()) continue;
sort(tmp[x].rbegin(), tmp[x].rend());
int j = 1;
for(auto i:tmp[x]){
while(j<=s&&i.second>0){
cnt[x][j++] = i.first;
i.second--;
}
}
mx[x] = j-1;
}
for(int w = 1; w<=s;w++){
fill(hlp, hlp+s+3, 0);
for(int sm = w;sm<=s;sm++){
if(hlp[sm-w]<mx[w]){
hlp[sm] = hlp[sm-w] + 1;
dp[sm] = max(dp[sm], dp[sm-w] + cnt[w][hlp[sm]]);
}
}
}
cout<<dp[s]<<endl;
return 0;
}
