#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define pll pair<ll,ll>
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update>
using ll=long long;
#define in insert
#define pb push_back
struct Node{
ll v;
ll w;
ll k;
ll ind;
bool operator<(const Node &other){
return w<other.w;
}
};
void solve(){
ll n,s;
cin>>s>>n;
vector<Node>v(n);
ll u,w,k;
vector<vector<ll>>cnt(s+1,vector<ll>(n));
for(int i=0;i<n;i++){
cin>>u>>w>>k;
v[i]={u,w,k,i};
for(int j=0;j<=s;j++){
cnt[j][i]=k;
}
}
vector<ll>dp(s+1,-1);\
dp[0]=0;
for(Node &n:v){
for(ll x=n.w;x<=s;x++){
if(dp[x-n.w]!=-1 && cnt[x-n.w][n.ind]>0 && dp[x]<dp[x-n.w]+n.v){
dp[x]=dp[x-n.w]+n.v;
cnt[x][n.ind]=cnt[x-n.w][n.ind]-1;
}
}
}
ll ans=0;
for(int i=s;i>=0;i--){
ans=max(ans,dp[i]);
}
cout<<ans;
}
int main(){
solve();
return 0;
}
