#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<ll> v(n), w(n), k(n);
for (int i = 0; i < n; ++i){
cin >> v[i] >> w[i] >> k[i];
}
vector<ll> dp(s + 1, -1);
dp[0] = 0;
for (int i = 0; i < n; ++i){
vector<ll> temp(s + 1);
vector<ll> tempDp(s + 1, -1);
for (int j = 0; j <= s; ++j){
if (j + w[i] <= s && dp[j] != -1){
tempDp[j + w[i]] = dp[j] + v[i];
temp[j + w[i]] = 1;
}
if (j + w[i] <= s && tempDp[j] > -1 && tempDp[j] + v[i] > tempDp[j + w[i]]){
if (temp[j] < k[i]){
tempDp[j + w[i]] = tempDp[j] + v[i];
temp[j + w[i]] = temp[j] + 1;
}
}
dp[j] = max(dp[j], tempDp[j]);
}
}
ll ans = 0;
for (int i = 0; i <= s; ++i) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
