#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, s;
cin >> s >> n;
vector<vector<ll>> a(n, vector<ll> (3));
for (int i = 0; i < n; ++i){
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
vector<ll> v, w;
vector<int> count(s + 1);
for (int i = 0; i < n; ++i){
if (count[a[i][1]] < s/a[i][1]){
while (count[a[i][1]] < s/a[i][1] && a[i][2] > 0){
v.push_back(a[i][0]);
w.push_back(a[i][1]);
a[i][2]--;
count[a[i][1]]++;
}
}
}
vector<ll> dp(s + 1, -1);
dp[0] = 0;
for (int i = 0; i < v.size(); ++i){
for (int j = s; j >= 0; --j){
if (j - w[i] >= 0 && dp[j - w[i]] != -1){
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
}
ll ans = 0;
for (int i = 0; i <= s; ++i) ans = max(dp[i], ans);
cout << ans << '\n';
return 0;
}
