#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;
for(int k=1; k<=c; k*=2){
items.push_back({k*w,k*val});
c -= k;
}
if(c>0){
items.push_back({c*w,c*val});
}
}
vector<int> dp(s+1,INT_MIN);
dp[0] = 0;
int maxi = 0;
for(auto pr : items){
for(int j=s; j>=pr.first; j--){
if (dp[j - pr.first] != INT_MIN){
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;
}
