#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];
f(i,0,n+1){
f(j,0,s+1) dp[i][j] = -1;
}
cout<<recurse(0, s, v, w, k, n);
}
return 0;
}
