#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll weight_limit,n;
cin >> weight_limit >> n;
vector<tuple<ll,ll,ll>> item(n);
for(auto &[a,b,c]: item) cin>> a >> b >> c;
vector<ll>dp(weight_limit+1,0);
for(ll i=0;i<n;i++){
ll weight=get<1>(item[i]),value=get<0>(item[i]);
for(ll j=weight_limit;j>=weight;j--){
ll count=min(get<2>(item[i]),(j/weight)+1);
while(count>0){ dp[j] = max(dp[j-(weight*count)]+(count*value),dp[j]); count--;}
dp[j] = max(dp[j],dp[j-1]);
}
}
cout << dp[weight_limit]<<endl;
return 0;
}
