#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
//using namespace __gnu_pbds;
//const int mod=1e9+7;
const int N=2e5+7;
const int mod=1e9+7;
const double INF=2e18;
const int lg=(1<<17);
//typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> order_set;
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,s;
cin >> s >> n;
vector <int> v(n),w(n),k(n);
vector <int> dp(s+1);
for(int i=0;i<n;i++){
cin >> v[i] >> w[i] >> k[i];
int j=1;
while(k[i]>0){
if(min(k[i],j)*w[i]<=s){
for(int kk=s;kk>=min(k[i],j)*w[i];kk--){
dp[kk]=max(dp[kk],dp[kk-min(k[i],j)*w[i]]+min(k[i],j)*v[i]);
}
}
k[i]-=min(k[i],j);
j<<=1;
}
}
int ot=0;
for(int i=0;i<=s;i++){
ot=max(ot,dp[i]);
}
cout << ot;
}
