#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int N, S;
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin >> S >> N;
vector<int> V(N), W(N), K(N);
for(int i = 0; i < N; i++) {
cin >> V[i] >> W[i] >> K[i];
}
vector<int> dp(S+1, -INF);
dp[0] = 0;
for(int i = 0; i < N; i++) {
for(int w = S; w >= 0; w--) {
// cout << i << ' ' << w << " " << dp[w] << endl;
for(int k = 1; k <= K[i] && w + W[i] * k <= S; k++) {
dp[w + W[i] * k] = max(dp[w + W[i] * k], dp[w] + V[i] * k);
}
}
}
cout << *max_element(dp.begin(), dp.end());
}
