#include<bits/stdc++.h>
using namespace std;
typedef vector<long long int> vi;
typedef vector<vi> vvi;
vvi dp;
vi values, weight, freqs;
int S, N;
long long int money(int wLeft, int item){
if(item < 0) return 0;
if(dp[wLeft][item] != -1) return dp[wLeft][item];
dp[wLeft][item] = money(wLeft, item-1);
for(int reps = 1; reps <= freqs[item]; ++reps){
if((long long)weight[item]*reps <= (long long)wLeft) dp[wLeft][item] = max(dp[wLeft][item], (long long)values[item]*reps + money(wLeft - weight[item]*reps, item-1));
else break;
}
return dp[wLeft][item];
}
int main(){
cin >> S >> N;
dp = vvi (S+1, vi(N, -1));
values = vi(N);
weight = vi(N);
freqs = vi(N);
for(int i = 0; i < N; ++i) cin >> values[i] >> weight[i] >> freqs[i];
cout << money(S, N-1) << endl;
return 0;
}
