#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
/***************************************************************** Template Start **************************************************************************/
#define endl "\n"
#define int long long
#define all(a) a.begin(), a.end()
// #define sort(a) sort(a.begin(), a.end())
#define sortrev(a) sort(a.rbegin(), a.rend())
#define prdouble(x) cout << fixed << setprecision(10) << x
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_greater_set;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_greater_multiset;
// find_by_order()
// order_of_key()
const int INF = 0x3f3f3f3f; // 1061109567
const int M = 1e9 + 7;
const int mod = 998244353;
void print(vector<int> v) { for(int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl;}
vector<int> input(int n) { vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; return a; }
vector<int> prime_factors(int n) { vector<int> prime; for(int i = 2; i*i <= n; i++) { while(n % i == 0) { prime.push_back(i); n /= i; } } if(n > 1) { prime.push_back(n); } return prime; }
vector<int> divisors(int n) { vector<int> v; for(int i = 1; i*i <= n; i++) { if(n % i == 0) { v.push_back(i); if(i != n / i) { v.push_back(n / i); } } } return v; }
int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b); }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
long long binMultiply(long long a, long long b, long long p) { long long ans = 0; a %= p; while(b > 0) { if(b & 1) { ans = (ans + a) % p; } a = (a + a) % p; b = b >> 1; } return ans; }
int binExp(int a, int b, int p)
{
if(b == 0) return 1;
a %= p;
if(b & 1) return (a * binExp(a, b - 1, p)) % p;
else return binExp((a * a) % p, b >> 1, p);
}
class DSU{
public:
vector<int> par, rank, size;
int n;
DSU(int sz)
{
n = sz;
rank.resize(n + 1, 0);
size.resize(n + 1);
par.resize(n + 1);
for(int i = 0; i <= n; i++)
{
par[i] = i;
size[i] = 1;
}
}
int find(int node)
{
if(node == par[node]) return node;
return par[node] = find(par[node]);
}
void merge(int u, int v)
{
u = find(u);
v = find(v);
if(u == v) return;
if(size[u] < size[v])
{
par[u] = v;
size[v] += size[u];
}
else
{
par[v] = u;
size[u] += size[v];
}
}
void mergeByRank(int u, int v)
{
u = find(u);
v = find(v);
if(u == v) return;
if(rank[u] < rank[v]) par[u] = v;
else if(rank[v] < rank[u]) par[v] = u;
else
{
par[v] = u;
rank[u] += 1;
}
}
};
/***************************************************************** Template End **************************************************************************/
void solve()
{
int s, n;
cin >> s >> n;
priority_queue<pair<int, int>> pq[s + 1];
for(int i = 0; i < n; i++)
{
int w, v, k;
cin >> v >> w >> k;
pq[w].push({v, k});
}
vector<int> dp(s + 1);
for(int w = 1; w <= s; w++)
{
int cnt = s / w;
while(!pq[w].empty() && cnt)
{
pair<int, int> p = pq[w].top();
pq[w].pop();
int value = p.first;
int freq = p.second;
freq = min(freq, cnt);
cnt -= freq;
for(int k = 1; k <= freq; k++)
{
for(int wt = s; wt >= w; wt--)
{
dp[wt] = max(dp[wt], dp[wt - w] + value);
}
}
}
}
int ans = 0;
for(int w = 1; w <= s; w++) ans = max(ans, dp[w]);
cout << ans << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
clock_t z = clock();
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
cerr << "Runtime : " << ((double)(clock() - z) / CLOCKS_PER_SEC) << endl;
return 0;
}
