#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;
#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define mp make_pair
void solve(){
int s,n;
cin>>s>>n;
vi v(n);
vi w(n);
vi k(n);
fori(i,n){
cin>>v[i]>>w[i]>>k[i];
}
map<int, vii> m;
fori(i,n){
m[w[i]].pb({v[i],k[i]});
}
vvi dp(2,vi(s+1,0));
int h = m.size();
int l=1;
int i=0;
for(auto x:m){
int wt = x.fi;
// cout<<wt<<" c";
l=!l;
rep(j,1,s){
dp[!l][j] = dp[l][j];
vii temp = m[wt];
int resw=0,resv=0;
sort(all(temp),greater<pii>());
fori(p,sz(temp)){
int t=0;
if(j-resw<0){
break;
}
while(t<=temp[p].se && j-t*wt-resw>=0){
dp[!l][j] = max( dp[!l][j], dp[l][j-t*wt-resw] + resv+t*temp[p].fi);
t++;
}
resw+=(t-1)*wt;
resv+=(t-1)*temp[p].fi;
}
// cout<<dp[!l][j]<<" ";
}
// cout<<endl;
i++;
}
int ans=0;
fori(i,s+1){
ans = max(ans,dp[h%2][i]);
}
// fori(i,n+1){
// fori(j,s+1){
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
// cin >> t;
while (t--)
{
solve();
}
}
