#include <bits/stdc++.h>
using namespace std;
#define ll 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;
struct SegTree {
int size = 1;
vector<int> tree;
SegTree (vector<int> &a){
while((int)a.size() > size)
size <<= 1;
tree.resize(size << 1);
for(int j = 0; j < (int)a.size(); j ++)
tree[size + j - 1] = a[j];
for(int j = (int)tree.size() - 1; j >= 0; j --)
tree[(j - 1) / 2] = max(tree[(j - 1) / 2], tree[j]);
}
int get(int l, int r, int x, int lx, int rx){
if(l <= lx and rx <= r)
return tree[x];
else if(r <= lx or rx <= l)
return INT_MIN;
int mid = (lx + rx) >> 1;
return max(get(l, r, (x << 1) + 1, lx, mid), get(l, r, (x << 1) + 2, mid, rx));
}
int get(int l, int r){
return get(l, r, 0, 0, size);
}
};
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 ++){
for(int j = 0; j < min(s + 1, w[i]); j ++){
vector<int> a;
for(int x = 0; x * w[i] + j <= s; x ++)
a.push_back(dp[x * w[i] + j] - x * v[i]);
SegTree st(a);
for(int x = 0; x * w[i] + j <= s; x ++){
int mx = st.get(max(0, x - k[i]), x + 1);
dp[x * w[i] + j] = max(dp[x * w[i] + j], mx + x * v[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;
}
}
