#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int s, n; cin >> s >> n;
vector<int> v(n), w(n), k(n);
for(int i=0; i<n; i++){
cin >> v[i] >> w[i] >> k[i];
k[i]= min(s/w[i]+1, k[i]);
}
vector<int> weight, value;
for(int i=0; i<n; i++){
int opt = k[i];
for(int x =1; x<=opt; x<<=1) {
value.push_back(x*v[i]);
weight.push_back(x*w[i]);
opt -= x;
}
if(opt>0) {
value.push_back(opt*v[i]);
weight.push_back(opt*w[i]);
}
}
vector<int> dp(2e3+10, 0);
for(int i=0; i<value.size(); i++){
for(int j =s+10; j>=weight[i]; j--){
dp[j]= max(dp[j], dp[j-weight[i]]+value[i]);
}
}
cout << dp[s]<< endl;
}
