#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char el = '\n';
const int maxn = 1e5+7;
const int maxw = 2007;
int n, W;
ll v[maxn], w[maxn], k[maxn];
ll dp_val[2][maxw], dp_cnt[2][maxw];
template<typename T>
void print(T a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << el; }
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
cin >> W >> n;
for (int i = 1; i <= n; i++) cin>>v[i], cin>>w[i], cin>>k[i];
for (int i = 1; i <= n; i++) {
int cur = i&1;
int prev = cur^1;
fill(dp_val[cur], dp_val[cur]+W+1, 0);
fill(dp_cnt[cur], dp_cnt[cur]+W+1, 0);
for (int j = 0; j <= W; j++) {
ll x=0, y=0;
ll cnt=0;
x = dp_val[prev][j];
if (j >= w[i]) {
y = dp_val[cur][j - w[i]];
cnt = dp_cnt[cur][j - w[i]];
if (cnt < k[i]) y += v[i], cnt++;
}
if (y > x) {
dp_val[cur][j] = y;
dp_cnt[cur][j] = cnt;
} else {
dp_val[cur][j] = x;
dp_cnt[cur][j] = 0;
}
}
// cout << el;
// cout << "prev: \n";
// print(dp_val[prev], W+1);
// print(dp_cnt[prev], W+1);
// cout << "cur:\n";
// print(dp_val[cur], W+1);
// print(dp_cnt[cur], W+1);
}
ll res = 0;
for (int i = 0; i <= W; i++) res = max(res, dp_val[n&1][i]);
cout << res;
// cout << el;
// print(dp_val[n&1], W+1);
// print(dp_cnt[n&1], W+1);
return 0;
}
