#include <bits/stdc++.h>
#define int long long
using namespace std;
int s,n;
vector<int> value, weight, copies;
void solve(){
cin>>s>>n;
value.resize(n+1);
copies.resize(n+1);
weight.resize(n+1);
int maxi = 0;
for(int i=0;i<n;i++){
cin>>value[i]>>weight[i]>>copies[i];
maxi = max(maxi, copies[i]);
}
vector<int> dp(s+1,0);
for(int i=0;i<n;i++){
for(int j=s;j>=0;j--){
for(int c = 0;(1LL<<c)<=copies[i];c++){
if(j>=(1LL<<c)*weight[i]) dp[j] = max(dp[j], ((1LL<<c)*value[i]) + dp[j - (1LL<<c)*weight[i]]);
}
}
}
cout<<dp[s]<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n_test = 1;
// cin>>n_test;
while(n_test--){
solve();
}
}
