#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++) {
if (arr[W].empty())
continue;
sort(arr[W].rbegin(), arr[W].rend());
ll br = s / W;
for (auto &[val, cnt] : arr[W]) {
if (br == 0)
break;
ll k = min(cnt, br);
br -= k;
for (int t = 0; t < k; t++)
for (ll w = s; w >= W; w--)
dp[w] = max(dp[w], dp[w - W] + val);
}
}
cout << dp[s] << endl;
}
