#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define endl '\n'
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;
#define printmp(a) for(auto x : a) cout << x[0] << ' ' << x[1] << endl;
const int mod = 1e9 + 7;
void solve(){
int s, n;
cin >> s >> n;
vector<int> v(n), w(n), k(n);
for(int i = 0; i < n; i ++)
cin >> v[i] >> w[i] >> k[i];
vector<int> dp(s + 1);
for(int i = 0; i < n; i ++){
vector<int> ndp(s + 1);
for(int j = 0; j < w[i]; j ++){
multiset<int> ml;
ml.insert(dp[j]);
for(int t = 1; t * w[i] + j <= s and t <= k[i]; t ++){
ndp[j + t * w[i]] = max(dp[j + t * w[i]], *ml.rbegin() + t * v[i]);
ml.insert(dp[j + t * w[i]] - t * v[i]);
}
for(int t = k[i] + 1; j + t * w[i] <= s; t ++){
ml.erase(ml.find(dp[j + (t - k[i] - 1) * w[i]] - (t - k[i] - 1) * v[i]));
ndp[j + t * w[i]] = max(dp[j + t * w[i]], *ml.rbegin() + t * v[i]);
ml.insert(dp[j + t * w[i]] - t * v[i]);
}
}
for(int i = 0; i <= s; i ++)
dp[i] = max(dp[i], ndp[i]);
}
cout << *max_element(all(dp));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
cout << endl;
}
}
