#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int s, n; cin >> s >> n;
map<int, vector<pii>> cnt;
for(int i = 0; i < n; i++) {
int v, w, k; cin >> v >> w >> k;
if (w <= s && k) cnt[w].push_back({v, k});
}
vector<vector<ll>> dp(sz(cnt)+1, vector<ll>(s+1, INT_MIN));
dp[0][0] = 0;
int curr = 1;
for(auto &[w, v] : cnt) {
sort(all(v)); reverse(all(v));
for(int i = 0; i <= s; i++) {
dp[curr][i] = dp[curr-1][i];
int idx = 0; int num = 0; int curr_num = 0;
ll money = 0;
while(1ll * (num+1) * w <= i && idx < sz(v)) {
num++;
money += v[idx].f;
if (dp[curr-1][i - num * w] != INT_MIN) {
dp[curr][i] = max(dp[curr][i], dp[curr-1][i - num * w] + money);
}
curr_num++;
if(curr_num == v[idx].s) {
curr_num = 0; idx++;
}
}
}
curr++;
}
cout << *max_element(all(dp.back())) << "\n";
return 0;
}
