#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define rsrt(x) sort(rall(x))
#define sz(x) (int)x.size()
#define fi first
#define se second
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vll>;
const ll inf=1e18;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll s, n; cin>>s>>n;
vll v(n), w(n), k(n); for(int i=0; i<n; i++) cin>>v[i]>>w[i]>>k[i];
vll dp(s+1);
for(int i=0; i<n; i++) for(int x=0; x<k[i]; x++){
for(int j=s; j>=w[i]; j--){
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
}
cout<<dp[s]<<'\n';
}
