#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];
}
vector<int> weight, value;
for(int i=0; i<n; i++){
int opt = k[i];
while(opt>0){
int x = pow(2, (62 - __builtin_clz(opt)));
opt-=x;
value.push_back(x*v[i]);
weight.push_back(x*w[i]);
}
}
vector<int> knapsack(sum+1, 0);
for(int i=0; i<value.size(); i++){
for(int j =sum; j>=weight[i]; j--){
knapsack[j]= max(knapsack[j], knapsack[j-weight[i]]+value[i]);
}
}
cout << knapsack[s]<< endl;
}
