#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int s, n; cin >> s >> n;
int sum =0;
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(k[i], 2000LL);
sum+=k[i]*w[i];
}
// cout << sum << endl;
vector<int> weight, value;
for(int i=0; i<n; i++){
int opt = k[i];
for(int x =1; x<=opt; x*=2) {
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]);
}
}
//for(int i: weight)cout << i << " ";
// cout << endl;
//for(int i: value)cout << i << " ";
vector<int> dp(sum+1, 0);
for(int i=0; i<value.size(); i++){
for(int j =sum; j>=weight[i]; j--){
dp[j]= max(dp[j], dp[j-weight[i]]+value[i]);
}
}
cout << dp[s]<< endl;
}
