#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;
#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));
const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
int32_t main(){
iShowSpeed;
int s, n; cin >> s >> n;
priority_queue <pii> pq[s + 1];
for (int i = 0; i < n; i++) {
int v, w, s; cin >> v >> w >> s;
pq[w].emplace(v, s);
}
vector <pii> a;
for (int i = 1; i <= s; i++) {
int cnt = (s + i - 1) / i;
while (!pq[i].empty()) {
auto [v, s] = pq[i].top(); pq[i].pop();
int ss = s;
while (cnt > 0 && ss > 0) a.emb(v, i), ss--, cnt--;
if (cnt == 0) break;
}
}
vector <int> dp(s + 1);
int ans = 0;
for (auto [v, w] : a) {
for (int i = s; i >= w; i--) {
dp[i] = max(dp[i], dp[i - w] + v);
ans = max(ans, dp[i]);
}
}
cout << ans;
}
