#include <bits/stdc++.h>
#include <unordered_map>
#define ull unsigned long long
#define ul unsigned long
#define ll long long
#define pb push_back
#define sodayoda_C ios_base::sync_with_stdio(false);cin.tie(NULL);
#define f(i,a,b) for(int i = a;i<b;i++)
#define fb(i,a,b) for(int i = a;i>b;i--)
#define endl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define MP make_pair
#define F first
#define S second
typedef std::vector<int> vi;
typedef std::pair<int, int> pi;
#define mod 1000000007
//memset(name,'',size)
//reverse(s,begin(),s.end())
using namespace std;
// ll dp[100001][2001];
// ll recurse(int i, int s, ll v[], ll w[], ll k[], int n){
// if(i == n) return 0;
// if(dp[i][s] != -1) return dp[i][s];
// ll ans = 0;
// for(int j = 0;j<=k[i];j++){
// if(s - j*w[i] >= 0) ans = max(ans, j*v[i] + recurse(i+1, s-j*w[i], v, w, k, n));
// else break;
// }
// return dp[i][s] = ans;
// }
int main(){
sodayoda_C;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
//cin>>t;
while(t--){
ll s, n;
cin>>s>>n;
ll v[n], w[n], k[n];
f(i,0,n) cin>>v[i]>>w[i]>>k[i];
//cout<<recurse(0, s, v, w, k, n);
ll dp[s+1], DP[s+1];
for(int i = 0;i<s+1;i++) DP[i] = 0;
for(int i = n-1;i>=0;i--){
for(int cs = 0;cs<s+1;cs++){
dp[cs] = 0;
for(int j = 0;j<=k[i];j++){
if(cs - j*w[i] >= 0) dp[cs] = max(dp[cs], j*v[i] + DP[cs - j*w[i]]);
else break;
}
}
for(int cs = 0;cs<s+1;cs++){
DP[cs] = dp[cs];
}
}
cout<<dp[s]<<endl;
}
return 0;
}
