#include <bits/stdc++.h>
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = (500*500)+1;
const int inf = 1e9;
const int mod=1e9+7;
struct edge{
int v,w;
};
bool cmp(edge a,edge b){
return a.w<=b.w;
}
vector<edge>v;
int dp[2005];
signed main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
boost
int n,s;
cin>>s>>n;
v.push_back({0,0});
for(int i=1;i<=n;i++){
edge x;
int k;
cin>>x.v>>x.w>>k;
int cnt=s/x.w;
k=min(k,cnt);
for(int j=1;j<=k;j++){
v.push_back(x);
}
}
sort(v.begin(),v.end(),cmp);
int ans=0;
for(int i=1;i<=v.size()-1;i++){
for(int j=s;j>=v[i].w;j--){
dp[j]=max(dp[j],dp[j-v[i].w]+v[i].v);
ans=max(ans,dp[j]);
}
}
cout<<ans;
}
