#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
ll s, n;
cin >> s >> n;
vector<vector<pair<ll, ll>>> arr(s + 1);
for (ll i = 0; i < n; i++) {
ll v, w, k;
cin >> v >> w >> k;
if (w > s)
continue;
arr[w].push_back({v, k});
}
vector<ll> dp(s + 1);
auto calc_dp = [&](ll val, ll W, ll pow) {
ll price = 1LL * val * pow, weight = 1LL * W * pow;
for (ll w = s; w >= weight; w--)
dp[w] = max(dp[w], dp[w - weight] + price);
};
for (ll W = 1; W <= s; W++) {
auto &vec = arr[W];
sort(vec.rbegin(), vec.rend());
ll br = 0;
for (auto &[val, cnt] : vec) {
ll k = min(cnt, s / W);
br += k;
if (br * W > s)
k -= br * W - s;
ll pow = 1;
while (k - pow > 0) {
k -= pow;
calc_dp(val, W, pow);
pow <<= 1;
}
if (k > 0)
calc_dp(val, W, pow);
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
