#include <bits/stdc++.h>
#define endline "\n"
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define lsb(i) i&(-i)
#define sz(i) (int)i.size()
typedef long long ll;
using namespace std;
const ll INF = 1e18L;
constexpr int mod = int(1e9) + 7;
ll t=1, n, m, k, q, s, cases = 0;
void solve(){
cin >> s >> n;
vector<ll> val(n),weight(n),amount(n);
for(int i = 0; i < n; i++){
cin >> val[i] >> weight[i] >> amount[i];
}
vector<ll> dp(s+10,0);
for(int i = 0; i < n; i++){
for(int j = 0; j < min(amount[i],(s / weight[i]) + 1); j++){
for(int k = s; k >= weight[i]; k--){
dp[k] = max(dp[k], dp[k - weight[i]] + val[i]);
}
}
}
ll ans = 0;
for(int i = 0; i <= s; i++)ans = max(ans,dp[i]);
cout << ans;
}
int main(){
#ifdef ONLINE_JUDGE
freopen("feast.in","r",stdin);
freopen("feast.out","w",stdout);
#endif
ios_base::sync_with_stdio(false);cin.tie(NULL);
//cin>>t;
for(; cases < t; cases++)solve();
return 0;
}
