#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define all(x) (x).begin(), (x).end()
ll dp[2001];
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int s, n;
cin >> s >> n;
vector<pair<ll, ll>> w[2001];
ll cur_v, cur_w, cur_k;
for (int i = 0; i < n; ++i) {
cin >> cur_v >> cur_w >> cur_k;
w[cur_w].push_back({cur_v, cur_k});
// ll c = 1;
// while (c < cur_k) {
// if (cur_w * c > s) {
// break;
// }
// w[c * cur_w].push_back(c * cur_v);
// cur_k -= c;
// c *= 2;
// }
// if (cur_k > 0) {
// if (cur_k * cur_w > s) continue;
// w[cur_k * cur_w].push_back(cur_k * cur_v);
// }
}
for (int i = 1; i <= s; ++i) { // cur_wright
sort(all(w[i]), greater<>());
int cur_cnt = 0;
for (int j = 0 ;j < w[i].size() && i * cur_cnt <= s; ++j) { // cur_cnt
while (w[i][j].second) {
if (i * cur_cnt > s) break;
cur_cnt++;
w[i][j].second--;
for (int k = s; k >= i; --k) {
dp[k] = max(dp[k], dp[k - i] + w[i][j].first);
}
}
}
}
cout << *max_element(dp, dp + s + 1) << '\n';
return 0;
}
