#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<ll> w[2001];
ll cur_v, cur_w, cur_k;
for (int i = 0; i < n; ++i) {
cin >> cur_v >> cur_w >> cur_k;
while(cur_k) {
cur_k--;
w[cur_w].push_back(cur_v);
}
// 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<ll>());
for (int j = 0 ;j < w[i].size() && i * j <= s; ++j) { // cur_cnt
for (int k = s; k >= i; --k) {
dp[k] = max(dp[k], dp[k - i] + w[i][j]);
}
}
}
cout << *max_element(dp, dp + s + 1) << '\n';
return 0;
}
