#include <bits/stdc++.h>
#define int long long
#define sz(x) (int)x.size()
using namespace std;
constexpr int maxn = 1e5 + 9, mod = 1e9 + 7;
struct Z{
int v, w, k;
bool operator<(const Z& other) const {
return v > other.v;
}
};
void solve() {
int s, n;
cin >> s >> n;
vector <Z> a(n + 1);
for(int i = 1; i <= n; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
a[i].k = min(a[i].k, s / a[i].w);
}
sort(a.begin() + 1, a.end());
vector <int> cnt(s + 1);
vector <int> dp(s + 100, -((int)1e11));
dp[0]=0;
vector <pair <int, int>> v;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < a[i].k && cnt[ a[i].w ] < s / a[i].w; j++) {
v.emplace_back( a[i].w, a[i].v );
cnt[a[i].w]++;
}
}
for(int i = 0; i < sz(v); i++) {
for(int j = s - v[i].first; j >= 0; j--) {
dp[j + v[i].first] = max(dp[j + v[i].first], dp[j] + v[i].second);
}
}
int ans = 0;
for(int i = 1; i <= s; i++) {
ans = max(ans, dp[i]);
}
cout << ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--) {
solve();
}
}
//
