#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
/**
* @brief Input
* s: Maximum Weight 1 <= s <= 2000
* n: Number of Items 1 <= n <= 100000 (1e5)
*
* v_i : Value of Item 1 <= v_i <= 1e6
* w_i : Weight of Item 1 <= w_i <= s
* k_i : Number of Items 1 <= k_i <= 1e9
*/
int s, n; std::cin >> s >> n;
std::map<int, std::vector<std::array<int, 2>>> items_by_weight;
for (int i = 0, v, w, k; i < n; ++i) {
std::cin >> v >> w >> k;
items_by_weight[w].push_back({v, k});
}
for (auto &[w, v] : items_by_weight)
std::sort(v.begin(), v.end(), std::greater<>());
/**
* dp[i][x]: Maximum value with i-item types and x-weight
*/
std::vector<int64_t> dp(s + 1, 0), dpOld;
for (auto &[w, vals]: items_by_weight) {
dpOld = dp;
int64_t profit = 0;
int totW = 0;
for (std::size_t i = 0; i < vals.size(); ) {
auto &[v, k] = vals[i];
if (k == 0) { ++i; continue; }
profit += v;
totW += w;
--k;
if (totW > s) break;
for (int x = 0; x <= s; x++) {
if (totW <= x)
dp[x] = std::max(dp[x], dpOld[x - totW] + profit);
}
}
}
std::cout << dp[s] << '\n';
return 0;
}
