#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vvll vector<vll>
#define vii vector<int>
#define vvii vector<vii>
#define vecs vector<string>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define vbl vector<bool>
#define vvbl vector<vector<bool>>
#define setpll set<pll>
#define setpii set<pii>
#define forl(i,a,b) for(ll i=a;i<b;i++)
#define fori(i,a,b) for(int i=a;i<b;i++)
#define rforl(i,a,b) for(ll i=a;i>b;i--)
#define rfori(i,a,b) for(int i=a;i>b;i--)
#define sz(a) a.size()
#define pb push_back
#define eb emplace_back
#define lexi lexicographical_compare
#define all(x) (x).begin(), (x).end()
#define suml(v) accumulate(all(v),0LL)
#define sumi(v) accumulate(all(v),0)
#define lb(v,target) lower_bound(all(v), target);
#define ub(v,target) upper_bound(all(v), target);
#define JOIN_STRINGS(vec) std::accumulate((vec).begin(), (vec).end(), std::string(""))
#define vin0(v) for(ll i=0; i<(ll)v.size(); i++) cin>>v[i];
#define vin1(v) for(ll i=1; i<(ll)v.size(); i++) cin>>v[i];
#define vini0(v) for(int i=0; i<(int)v.size(); i++) cin>>v[i]
#define vini1(v) for(int i=1; i<(int)v.size(); i++) cin>>v[i];
#define vout0(v) for(ll i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vout1(v) for(ll i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vouti0(v) for(int i=0; i<(ll)v.size(); i++) cout<<v[i]<<' '
#define vouti1(v) for(int i=1; i<(ll)v.size()+1; i++) cout<<v[i]<<' '
#define fastIO() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF INT32_MAX
const int MOD=1e9+7;
const int MAX_N = 100005;
#define add(a,b) a=(a+(b))%MOD
using namespace std;
//Tarjans Bridge Finding algo
// int bridgec;
// vector<int> adj [MAX_N];
// int dfs [MAX_N];
// int low [MAX_N];
// int cur;
//
// void visit (int vertex, int parent) {
// cur++;
// dfs[vertex] = cur;
// low[vertex] = cur;
//
// for (int nxt : adj[vertex]) {
// if (dfs[nxt] == 0) {
// visit(nxt, vertex);
// low[vertex] = min(low[vertex], low[nxt]);
// if (low[nxt] > dfs[vertex]) {
// bridgec++;
// }
// } else if (nxt != parent) {
// low[vertex] = min(low[vertex], dfs[nxt]);
// }
// }
// }
// void setIO(string name = "") {
// if (name.size()) {
// freopen((name + ".in").c_str(), "r", stdin);
// freopen((name + ".out").c_str(), "w", stdout);
// }
// }
int main () {
fastIO();
int s,n;cin>>s>>n;
map<int,vpii>weight;
fori(i,0,n) {
int v,w,k;cin>>v>>w>>k;
if (w<=s && v>0) weight[w].pb({v,k});
}
vvll dp(weight.size()+1,vll(s+1,INT32_MIN));
dp[0][0]=0;
int pos=1;
for (auto [w,items]:weight) {
sort(all(items),greater<pii>());
fori(i,0,s+1) {
dp[pos][i]=dp[pos-1][i];
ll profit=0;
int tot_copies=0;
int curr_copies=0;
int items_iter=0;
while ((tot_copies+1)*w<=i && items_iter<items.size()) {
tot_copies++;
profit++;
dp[pos][i]=max(dp[pos][i],dp[pos-1][i-(tot_copies*w)]+profit);
curr_copies++;
if (curr_copies==items[items_iter].second) {
curr_copies=0;
profit=0;
items_iter++;
}
}
}
pos++;
}
cout << *max_element(all(dp.back())) << endl;
//dp[i][j]=max value till ith weight type and j weight = max(dp[i][j],dp[i-1][j-(copies*w[i])]+profit
}
