#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, min(k, s / w)});
}
vector<ll> dp(s + 1);
for (ll W = 1; W <= s; W++) {
for (auto &[val, cnt] : arr[W]) {
ll k = min(cnt, s / W);
ll pow = 1;
while (k > 0) {
ll take = min(pow, k);
k -= take;
pow <<= 1;
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);
}
}
}
cout << dp[s] << endl;
}
