#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define forn(i,start,end) for(int i=start;i<end;i++)
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int main(){
int s,n;
cin>>s>>n;
vvi a(n,vi(3));
forn(i,0,n){
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
vvi dp(n+1,vi(s+1));
forn(i,1,n+1){
forn(j,1,s+1){
dp[i][j]=dp[i-1][j];
for(int k=1;k<=a[i-1][2] && a[i-1][1]*k<=j;k++){
dp[i][j]=max(dp[i][j],a[i-1][0]*k +dp[i-1][j-k*a[i-1][1]]);
}
}
}
cout<<dp[n][s]<<endl;
}
