#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int mxS=2e3;
ll dp[mxS+1];
map<ll, ll> mp[mxS+1];
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int s, n; cin>>s>>n;
vector<array<ll, 3>> v(n);
for(int i=0; i<n; i++) {
cin>>v[i][0]>>v[i][1]>>v[i][2];//v, w, k
mp[v[i][1]][v[i][0]]+=v[i][2];
}
/* for(int i=0; i<n; i++) {
ll use=v[i][2];
for(int j=1; use>0; j*=2) {
ll x=min(use, j)*v[i][1];
ll val=1ll*min(use, j)*v[i][0];
for(int k=s; k>=x; k--) {
dp[k]=max(dp[k], dp[k-x]+val);
ans=max(ans, dp[k]);
}
use-=min(use, j);
}
}
*/
for(int i=1; i<=s; i++) {
int mx=s/i;
for(auto it=mp[i].rbegin(); it!=mp[i].rend(); it++) {
if(mx==0)
break;
auto [v, c]=*it;
int use=min(mx, c);
int base=1;
c=use;
while(c>0) {
int tmp=min(c, base);
for(int j=s; j>=tmp*i; j--) {
dp[j]=max(dp[j], dp[j-tmp*i]+tmp*v);
}
c-=tmp;
base*=2;
}
mx-=use;
}
}
cout<<dp[s];
return 0;
}
