#include <bits/stdc++.h>
// #include <vector>
// #include <iostream>
// #include <map>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
typedef pair<ll,ll> pll;
typedef pair<char,char> pcc;
int h[] = {1,-1,0,0};
int v[] = {0,0,1,-1};
const ll N = 1e6+1;
const ll INF = LLONG_MAX;
ll p[N];
vector<vector<pair<ll,ll>>> adj;
// ll dist[N];
vector<ll> dist(N, INF);
void dijkstra(ll s, vector<ll> &parent){
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[s] = 0;
pq.push({0, s});
while(!pq.empty()){
ll vert = pq.top().second;
ll dv = pq.top().first;
pq.pop();
if(dist[vert]!=dv) continue;
for(auto x : adj[vert]){
if(dist[x.first] > dist[vert]+x.second){
dist[x.first] = dist[vert]+x.second;
pq.push({dist[x.first], x.first});
}
}
}
}
void printv(vector<ll> a)
{
for(ll i=0; i<a.size(); i++)
{
cout << a[i] << ' ';
}
cout << '\n';
}
string operator * (string a, unsigned int b) {
string output = "";
while (b--) {
output += a;
}
return output;
}
// const int INF = 1000000000;
// vector<vector<pair<int, int>>> adj;
void dijkstra(int s, vector<ll> & d, vector<int> & p) {
int n = adj.size();
d.assign(n, INF);
p.assign(n, -1);
vector<bool> u(n, false);
d[s] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,s});
while(!pq.empty()){
int v = pq.top().second;
int dv = pq.top().first;
pq.pop();
if(dv!=d[v])continue;
u[v]=true;
for(auto e : adj[v]){
if(d[e.first] > d[v]+e.second){
d[e.first] = d[v]+e.second;
pq.push({d[e.first],e.first});
}
}
}
}
int dp[N] = {0};
ll logg = 50;
// vector<vector<int>> grid(N, vectr);
const ll yo = 2e5 + 1;
ll lookup_table[yo] = {};
ll fib_mem(ll n);
ll fib(ll n) { return n <= 1 ? n : fib_mem(n-1) + fib_mem(n-2); }
ll fib_mem(ll n)
{
if (lookup_table[n] == 0) {
lookup_table[n] = fib(n);
}
return lookup_table[n];
}
void solve()
{
ll s, n; cin >> s >> n;
map<ll, vector<pll>> mp;
for(ll i=0; i<n; i++){
ll v, w, k;
cin >> v >> w >> k;
if(k>=1)mp[w].push_back(make_pair(v, k));
}
vector<vector<ll>> dp(mp.size()+1, vector<ll>(s+1, LLONG_MIN));
dp[0][0] = 0;
ll allowed = 1;
for(auto &[weight, items] : mp){
sort(items.begin(), items.end(), greater<pll>());
for(ll i=0; i<=s; i++){
dp[allowed][i] = dp[allowed-1][i];
ll cnt = 0, curitem = 0;
ll earn = 0;
ll used =0;
while((cnt+1)*weight <= i && curitem<items.size()){
cnt++;
auto [val, maxcopies] = items[curitem];
earn+=val;
if(dp[allowed-1][i-cnt*weight]!=LLONG_MIN){
dp[allowed][i] = max(dp[allowed][i], dp[allowed-1][i-cnt*weight] + earn);
}
used++;
if(used==maxcopies){
used = 0;
curitem++;
}
}
}
allowed++;
}
cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}
//dsu
/*
ll parent[N];
ll si[N];
ll sets = 0;
void make_set(ll v)
{ //size based
parent[v] = v;
si[v] = 1;
sets++;
}
ll find_set(ll v)
{
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]); //path compression
}
void union_sets(ll a, ll b)
{
a = find_set(a);
b = find_set(b);
if (a != b)
{
if (si[a] < si[b])
swap(a, b);
parent[b] = a;
if (si[a] == si[b])
si[a]++;
sets--;
}
}
*/
/*
// to use unordered hash map on a pair
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
// Hash the first element
size_t hash1 = hash<T1>{}(p.first);
// Hash the second element
size_t hash2 = hash<T2>{}(p.second);
// Combine the two hash values
return hash1
^ (hash2 + 0x9e3779b9 + (hash1 << 6)
+ (hash1 >> 2));
}
};
// unordered_map<pair<int,int>, string, hash_pair> paths;
*/
// bool dfs(ll start, ll parent, vector<ll> &ans)
// {
// vis[row][col] = 1;
// cout << "visiting " << g[x][y] << " curvol = " << curvol;
// for(ll i=0; i<4; i++)
// {
// ll dx = h[i]; ll dy = v[i];
// if(x+dx<n && y+dy<m && x+dx>=0 && y+dy>=0 && g[x+dx][y+dy] && !vis[x+dx][y+dy])
// {
// dfs(g,x+dx,y+dy,n,m);
// }
// }
// }
int main()
{
// cout << log2(9)/log2(3) << '\n';
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// ll t;
// cin >> t;
// while(t--)
// {
// solve();
// }
solve();
}
