#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int s,n;
cin>>s>>n;
vector<int> prices(n);
vector<int> size(n);
vector<int> copies(n);
for(int i=0; i<n; i++){
cin>>prices[i];
cin>>size[i];
cin>>copies[i];
}
vector<pair<int,int>>items;
for(int i=0; i<n; i++){
int val = prices[i];
int w = size[i];
int c = copies[i];
int curr_c = 1;
while(c>0){
int item = min(curr_c, c);
items.push_back({w*curr_c,val*curr_c});
c -= curr_c;
}
}
vector<int> dp(s+1,INT_MIN);
dp[0] = 0;
int maxi = -1;
for(auto pr : items){
for(int j=s; j>=pr.first; j--){
dp[j] = max(dp[j],pr.second+dp[j-pr.first]);
maxi = max(maxi,dp[j]);
}
}
cout<<maxi<<endl;
}
signed main() {
int t=1;
// cin>>t;
while (t--) {
solve();
}
return 0;
}
