#include <bits/stdc++.h>
using namespace std;
int main() {
int S, N; cin >> S >> N;
int V[100001], W[100001], K[100001];
for (int i = 0; i < N; i++){
cin >> V[i] >> W[i] >> K[i];
}
int dp[2][2000];
for (int i = 0; i < 2000; i++){
dp[0][i] = -1;
dp[1][i] = -1;
}
int curr = 0, next = 1;
for (int i = 0; i <= K[0]; i++){
dp[curr][i*W[0]] = i*V[0];
}
for (int i = 0; i < N; i++){
curr = i%2; next = (i+1)%2;
for (int s = 0; s <= S; s++){
if (dp[curr][s] == -1){
// cout << i << " " << s << " " << dp[curr][s] << endl;
continue;
}
for (int k = 0; k <= K[i+1]; k++){
if (s+k*W[i+1] > S) break;
dp[next][s+k*W[i+1]] = max(dp[curr][s] + k*V[i+1], dp[next][s+k*W[i+1]]);
}
// cout << i << " " << s << " " << dp[curr][s] << endl;
}
}
int ans = 0;
for (int i = 0; i <= S; i++){
ans = max(ans, dp[(N-1)%2][i]);
}
cout << ans;
}
