#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);
int s, n;
cin >> s >> n;
unordered_map<int, vector<pair<int, int>>> mp;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
mp[w].push_back({v, k});
}
vector<ll> dp(s + 1);
auto calc_dp = [&](int val, int W, int pow) {
ll price = 1LL * val * pow, weight = 1LL * W * pow;
for (int w = s; w >= weight; w--)
dp[w] = max(dp[w], dp[w - weight] + price);
};
for (auto &[W, vec] : mp) {
sort(vec.rbegin(), vec.rend());
int br = 0;
for (auto &[val, cnt] : vec) {
int k = min(cnt, s / W);
br += k;
ll pow = 1;
while (k - pow > 0) {
k -= pow;
calc_dp(val, W, pow);
pow <<= 1;
}
if (k <= 0)
break;
calc_dp(val, W, k);
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
