#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<ll, ll>
#define f first
#define s second
int main(){
int s, n; cin>>s>>n;
vector<int> v(n+1);
vector<int> w(n+1);
vector<int> k(n+1);
for (int i=1; i<=n; i++){
cin>>v[i]>>w[i]>>k[i];
}
vector<vector<pr>> dp(n+1, vector<pr>(s+1, {0, 0}));
for (int i=1; i<=n; i++){
for (int j=0; j<=s; j++){
if(j+w[i]<=s){
// from the same row
if((dp[i][j].f>0 || j==0) && dp[i][j].s<k[i]) {
dp[i][j+w[i]].f=max(dp[i][j+w[i]].f, dp[i][j].f+v[i]);
dp[i][j+w[i]].s=dp[i][j].s+1;
}
// from previous row
if(dp[i-1][j].f>0){
dp[i][j+w[i]].f=max(dp[i][j+w[i]].f, dp[i-1][j].f+v[i]);
dp[i][j+w[i]].s=1;
}
}
}
}
/*
for (int j=1; j<=s; j++) cout<<j<<" ";
cout<<endl;
for (int i=1; i<=n; i++){
for (int j=1; j<=s;j++){
cout<<dp[i][j].f<<" ";
}
cout<<endl;
}
for (int j=1; j<=s;j++) cout<<j<<" ";
cout<<endl;
for (int i=1; i<=n; i++){
for (int j=1; j<=s;j++){
cout<<dp[i][j].s<<" ";
}
cout<<endl;
}
*/
ll results=0;
for (int i=1; i<=n; i++){
for (int j=s; j>=0;j--){
if(dp[i][j].f>0) {
results=max(results, dp[i][j].f);
break;
}
}
}
cout<<results;
}
