#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
const int N = 1e6+9;
const int INF = 1e18;
int k,n;
vector<int> dp;
vector<pair<int,int>> vp;
void solve(){
cin >> k >> n;
for(int i=0;i<n;i++){
int a,b,c;cin >> a >> b >> c;
while(c--){
vp.emplace_back(a,b);
}
}
dp.assign(k+1,0);
for(auto &x:vp){
int price=x.first,weight=x.second;
for(int i=k;i>=weight;i--){
dp[i]=max(dp[i],dp[i-weight]+price);
}
}
cout << dp[k] << "\n";
// for(int i=1;i<=k;i++){
// cout << i << " " << dp[i] << "\n";
// }
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int q=1;
// cin >> q;
while(q--)solve();
return 0;
}
