#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
/*
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
15
=================
20 3
5000 15 1
100 1 3
50 1 4
5400
The housewife take one of item 1, three of item 2 and two of item 3 for a total weight of
15 × 1 + 1 × 3 + 1 × 2 = 20 and a total value of 5000 × 1 + 100 × 3 + 50 × 2 = 5400.
*/
int main()
{
ll S, N;
cin >> S >> N;
vector<ll> V(N+1, 0);
vector<ll> W(N+1, 0);
vector<ll> K(N+1, 0);
for (int i = 1; i <= N; i++) {
ll v,w,k;
cin >> v >> w >> k;
V[i] = v;
W[i] = w;
K[i] = k;
}
vector<vector<ll>> dp(S+1, vector<ll>(N+1, 0));
for(ll s = 1; s <= S; s++) {
for(ll n = 1; n <= N; n++) {
dp[s][n] = dp[s][n-1];
for(ll k = 1; k <= K[n]; k++) {
if (W[n] * k <= s) {
if ((dp[s-W[n]*k][n-1] + V[n]*k) > dp[s][n]) {
dp[s][n] = dp[s-W[n]*k][n-1] + V[n]*k;
}
}
}
}
}
/*
for(int i = 0; i <= S; i++) {
cout << "s = " << i << ":";
for(ll j = 0; j <= N; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
*/
cout << dp[S][N];
return 0;
}
