#include <bits/stdc++.h>
using namespace std;
int main() {
int S, N; cin >> S >> N;
long long V[100002], W[100002], K[100002];
for (int i = 0; i < N; i++){
cin >> V[i] >> W[i] >> K[i];
}
long long dp[2][2002];
for (int i = 0; i < 2002; i++){
dp[0][i] = -1;
dp[1][i] = -1;
}
int curr = 0, next = 1;
for (int i = 0; i <= K[0] && i*W[0] <= S; i++){
dp[curr][i*W[0]] = i*V[0];
}
for (int i = 0; i < N-1; 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;
}
}
long long ans = 0;
for (int i = 0; i <= S; i++){
ans = max(ans, dp[(N-1)%2][i]);
}
cout << ans << endl;
}
