#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, n;
if (!(cin >> S >> n)) return 0;
vector<vector<pair<int,long long>>> E(S + 1);
for (int i = 0; i < n; ++i) {
int v, w; long long k;
cin >> v >> w >> k;
if (w <= S) E[w].push_back({v, k});
}
vector<long long> dp_prev(S + 1, 0), dp_curr;
for (int weight = 1; weight <= S; ++weight) {
dp_curr = dp_prev;
for (auto &it : E[weight]) {
long long val = it.first;
long long cnt = it.second;
long long takePow = 1;
while (cnt > 0) {
long long take = min(takePow, cnt);
cnt -= take;
int wtot = int(take * weight);
long long vtot = val * take;
for (int cap = S; cap >= wtot; --cap) {
dp_curr[cap] = max(dp_curr[cap], dp_curr[cap - wtot] + vtot);
}
takePow <<= 1;
}
}
dp_prev.swap(dp_curr);
}
long long ans = 0;
for (int c = 0; c <= S; ++c) ans = max(ans, dp_prev[c]);
cout << ans << '\n';
return 0;
}
