#include <bits/stdc++.h>
using namespace std;
long long CalculateKnapsack(int S, vector<array<long long,3>> &items){
int n = items.size();
sort(items.begin(),items.end());
// v, w, k
vector<long long> dp(S+1,0);
long long ans = 0;
for(int i = 0; i < n; i++){
for(int j = S; j >= 0; j--){
for(int t = 1; t <= items[i][2] && j - t * items[i][1] >= 0; t++){
dp[j] = max(dp[j], dp[j - t * items[i][1]] + t * items[i][0]);
ans = max(ans,dp[j]);
}
}
}
return ans;
}
int32_t main(){
cin.tie(nullptr)->sync_with_stdio(0);
int S; int N;
cin >> S >> N;
vector<array<long long,3>> items(N);
for(auto &[V,W,K] : items){
cin >> V >> W >> K;
}
cout << CalculateKnapsack(S,items) << '\n';
}
