#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
signed main(){
fastio();
// #ifndef ONLINE_JUDGE
// freopen("input1.txt","r",stdin);
// freopen("output1.txt","w",stdout);
// #endif
//games and constructive mein hamesha test cases banakar dekho aur unpe solve karne ki
//koshish karo.recursive approach type.
int s,n; cin>>s>>n;
vector<vector<int>>v(n+1,vector<int>(3));
for(int i=1; i<=n; i++){
int a,b,c;
cin>>a>>b>>c;
v[i][0]=a;v[i][1]=b;v[i][2]=c;
}
int dp[n+1][s+1];
for(int i=0; i<=n; i++){
for(int j=0; j<=s; j++){
dp[i][j]=0;
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=s; j++){
for(int k=0; k<=v[i][2]; k++){
if(j>=(k*v[i][1])){
dp[i][j]=max(dp[i][j],dp[i-1][j-(k*v[i][1])]+k*v[i][0]);
}
}
}
}
cout<<dp[n][s]<<endl;
return 0;
}
