#include <bits/stdc++.h>
using namespace std;
// clang-format off
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl "\n"
#define pb push_back
#define sz(v) int(v.size())
#define mems(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define forn(i,s,e) for(int i = s; i < (e); ++i)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
for ( \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
blockTime.second; \
debug("%s : %lld ms\n ", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false)
const int M = 1e9 + 7;
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
#ifdef LOCAL
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
#else
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (auto v : vec) os << v << ' '; return os; }
#endif
template <class T> T ABS(const T &x) {return x>0? x:-x;}
ll gcd(ll n1, ll n2) {return n2==0? ABS(n1) : gcd(n2,n1%n2);}
ll lcm(ll n1, ll n2) {return n1==0 && n2==0? 0 : ABS(n1*n2)/gcd(n1,n2);}
ll ceil2(ll a, ll b) {return (a + b - 1) / b;}
template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template <typename T> vector<T> sorttrunq(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
// clang-format on
// int dx[4] = {1,-1,0,0};
// int dy[4] = {0,0,1,-1};
/*
1. When multiplying always consider the possiblity of overflow.
*/
struct Item {
ll v, w, k;
};
void solve() {
int s, n;
cin >> s >> n;
map<ll, vpll> W;
forn(i, 0, n) {
ll v, w, k;
cin >> v >> w >> k;
W[w].push_back({v, k});
}
vl dp(s + 1, 0);
for (auto &[w, items] : W) {
sort(items.rbegin(), items.rend());
for (int wt = s; wt >= 0; --wt) {
int idx = 0, cnt = 0, currItemCnt = 0;
ll profit = 0;
while ((cnt + 1) * w <= wt && idx < sz(items)) {
++cnt;
++currItemCnt;
profit += items[idx].first;
chmax(dp[wt], dp[wt - cnt * w] + profit);
if (currItemCnt == items[idx].second) {
++idx;
currItemCnt = 0;
}
}
}
}
cout << dp[s] << endl;
}
int main() {
FASTIO
int t = 1;
while (t--) {
solve();
}
return 0;
}
