#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll s, n; cin >> s >> n;
vector<ll> weight(1), profit(1);
for (int i = 0; i < n; i++) {
ll v, w, k; cin >> v >> w >> k;
ll amount = min(s/w + 1, k);
for (int j = 0; j < amount; j++) {
weight.push_back(w);
profit.push_back(v);
}
}
n = weight.size();
vector<vector<ll>> dp(s+1, vector<ll>(n, 0));
for (ll w = 1; w <= s; w++) {
for (int i = 1; i < n; i++) {
dp[w][i] = dp[w][i-1];
if (w-weight[i] >= 0) {
dp[w][i] = max(dp[w][i], profit[i] + dp[w-weight[i]][i-1]);
}
}
}
cout << dp[s][n-1] << endl;
return 0;
}
