// #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<ll> d(s+1,-inf);
d[0] = 0;
for (auto &[w,q] : a)
{
sort(q.rbegin(),q.rend());
for (int i=s; i>=0; i--)
{
ll p = 0, r = 0;
for (auto [v,k] : q)
for (int l = 0; l<k && p<i/w; l++,p++,r+=v)
if (d[i-(p+1)*w]!=-inf) d[i] = max(d[i],d[i-(p+1)*w]+r+v);
}
}
ll res = *max_element(d.begin(),d.end());
cout << res << "\n";
}
