#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];
int cur_v, cur_w, cur_k;
for (int i = 0; i < n; ++i) {
cin >> cur_v >> cur_w >> cur_k;
int 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;
}
