#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll s, n, v, w, k, r=0, a;
cin>>s>>n;
vector<ll> dp(s+100, -1);
dp[0]=0;
vector<vector<pair<ll,ll> > > ord(s+1);
for(int i=1;i<=n;i++){
cin>>v>>w>>k;
ord[w].push_back({v, k});
}
for(int i=1;i<=s;i++){
if(ord[i].size() > 0){
sort(ord[i].rbegin(), ord[i].rend());
a = s/i;
for(int j=0;j<ord[i].size();j++){
if(a > 0){
for(int k=1;k<=min(a, ord[i][j].second);k++){
for(int p=s;p>=0;p--){
if(dp[p] != -1){
if(p+i <= s){
dp[p+i] = max(dp[p+i], dp[p]+ord[i][j].first);
}
}
}
}
a -= ord[i][j].second;
}
if(a <= 0)break;
}
}
}
for(int i=1;i<=s;i++)r=max(r, dp[i]);
cout<<r<<ENDL;
return 0;
}
