#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#ifdef imtiyazrasool92
#include "algos/debug.h"
#else
#define dbg(...) 92
#endif
void run_case() {
int S, N;
cin >> S >> N;
// vi,wi,ki
vector<array<int64_t, 3>> A(N);
for (auto &[x, y, z] : A)
cin >> x >> y >> z;
// store number of times current element is used,max score can achieve
vector<array<int64_t, 2>> dp(S + 1, { -1, -1});
dp[0] = {0, 0};
for (int i = 0; i < N; i++) {
for (int j = A[i][1]; j <= S && A[i][2] > 0; j++) {
int reach = j - A[i][1];
if (dp[reach] != array<int64_t, 2> { -1, -1}) {
array<int64_t, 2> can_be = dp[reach];
can_be[1] += A[i][0];
can_be[0]++;
if (can_be[0] <= A[i][2] && can_be[1] > dp[j][1]) {
dp[j] = can_be;
}
}
}
for (int j = 0; j <= S; j++)
if (dp[j] != array<int64_t, 2> { -1, -1})
dp[j][0] = 0;
}
int64_t answer = 0;
for (int s = 0; s <= S; s++)
answer = max<int64_t>(answer, dp[s][1]);
cout << answer;
}
int32_t main() {
ios::sync_with_stdio(false);
#ifndef imtiyazrasool92
cin.tie(nullptr);
#endif
int tests = 1;
// cin >> tests;
while (tests--) {
run_case();
cout << '\n';
}
return 0;
}
