// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ui = unsigned int;
using ul = unsigned long long;
using i128 = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using t3i = tuple<int, int, int>;
using t3l = tuple<ll, ll, ll>;
using vi = vector<int>;
using vl = vector<long long>;
using vb = vector<bool>;
using vp = vector<pair<ll, ll>>;
using arr = array<int, 4>;
using node = pair<int, arr>;
template <class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll inf = 1e18;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int s, n; cin >> s >> n;
map<int, vp> a;
for (int i = 0; i < n; i++)
{
int v, w, k; cin >> v >> w >> k;
a[w].push_back({v,k});
}
vector<vl> d(a.size()+1,vl(s+1,-inf));
d[0][0] = 0;
int i = 1;
for (auto &[w,q] : a)
{
sort(q.rbegin(),q.rend());
for (int j = 0; j <= s; j++)
{
ll p = 0, r = 0;
d[i][j] = d[i-1][j];
for (auto [v,k] : q)
for (int l = 0; l < k && p<j/w; l++)
{
p += 1, r += v;
if (d[i-1][j-p*w]!=-inf) d[i][j] = max(d[i][j],d[i-1][j-p*w]+r);
}
} i += 1;
}
ll res = -inf;
for (int i = 0; i <= s; i++) res = max(res,d[a.size()][i]);
cout << res << "\n";
}
