// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main() {
LL S, N; cin >> S >> N;
LL V[N+1]; memset(V,0,sizeof(V));
LL W[N+1]; memset(W,0,sizeof(W));
LL K[N+1]; memset(K,0,sizeof(K));
for (LL i = 1; i <= N; i++) {
cin >> V[i] >> W[i] >> K[i];
}
LL dp[2][S+1];
for (LL i = 0; i < 2; i++) {
dp[i][0] = 0;
for (LL j = 1; j < S+1; j++) {
dp[i][j] = -1;
}
}
for (LL i = 1; i <= N; i++) {
LL ind = i%2;
LL oi = (i+1)%2;
for (LL j = S; j >= 0; j--) {
dp[ind][j] = dp[oi][j];
if (dp[ind][j] < 0) continue;
for (LL w = W[i],c=1; w+j <= S && c<=K[i]; w+=W[i],c++) {
dp[ind][w+j] = max(dp[ind][w+j], dp[ind][j]+V[i]*c);
}
}
}
LL res = 0;
for (LL i = 1; i <= S; i++) {
res = max(res, dp[N%2][i]);
}
cout << res << endl;
}
