#include<bits/stdc++.h>
using namespace std;
#define task ""
#define f first
#define s second
#define FOR(i,a,b) for(int i = a;i<=b;i++)
#define FOU(i,a,b) for(int i = a;i>=b;i--)
#define times cerr<<endl<<"time:"<<(1.0*clock())/CLOCKS_PER_SEC<<endl;
mt19937 rng(time(nullptr));
int rand(int l,int r){return l+rng()%(r-l+1);}
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
template<class X,class Y>
bool maximize(X &x,const Y &y){
if(x<y){
x = y;
return false;
}else return true;
}
template<class X,class Y>
bool minimize(X &x,const Y &y){
if(x>y){
x = y;
return false;
}else return true;
}
const int sz = 1e5+5;
const int mz = 2e2+5;
int n,S;
ll dp[mz];
ll w[mz],vl[mz],k[mz],used[mz];
bool cmp(int a,int b){
return vl[a]>vl[b];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>S>>n;
FOR(i,1,n)cin>>vl[i]>>w[i]>>k[i];
vi ord(n);
iota(ord.begin(),ord.end(),1);
sort(ord.begin(),ord.end(),cmp);
for(int i:ord){
FOR(it,1,k[i]){
if(used[w[i]]*w[i]>S)break;
FOU(j,S,w[i])maximize(dp[j],dp[j-w[i]]+vl[i]);
used[w[i]]++;
}
}
cout<<dp[S];
}
