#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7 ;
#define int long long // safety
int S , N ;
int dp[2002][2002] ;
int w[2002] ;
int v[2002] ;
int cnt[2002] ;
int rec(int i,int x ){
if(i==N) return 0 ;
if(dp[i][x] != -1){
return dp[i][x] ;
}
int ans = 0 ;
for(int k=0 ; k <= min(cnt[i], x/w[i] ) ; k++){
if(k*w[i]<=x){
ans = max(ans, rec(i+1 , x- k*w[i]) + k*v[i]) ;
}else{
break ;
}
}
return dp[i][x] = ans ;
}
void solve(){
cin>>S>>N;
memset(dp,-1,sizeof(dp)) ;
for(int i=0 ; i<N ; i++){
cin>>v[i]>>w[i]>>cnt[i] ;
}
int d = rec(0,S) ;
cout<<d<<endl ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1 ;
// cin >> t;
while(t--) solve();
return 0;
}
