#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 1e5 + 5;
constexpr int SUMMAX = 2005;
typedef long long LL;
struct Item {
int value;
int weight;
int copies;
bool operator < (const Item &other) const {
return (weight < other.weight || (weight == other.weight && value < other.value));
}
};
int S, N;
Item V[NMAX];
LL dp[SUMMAX];
int main () {
cin >> S >> N;
for (int i = 1; i <= N; ++ i )
cin >> V[i].value >> V[i].weight >> V[i].copies;
sort(V+1, V+N+1);
for (int i = 1; i <= S; ++ i )
dp[i] = -1;
for (int i = 1; i <= N; ++ i ) {
LL cnt = 0;
int dr = i;
while (dr <= N && V[dr].weight == V[i].weight) {
cnt += 1LL * V[dr].copies;
++ dr;
}
int ind = i;
int w = V[i].weight;
for (int nr = 1; ind < dr && 1LL * nr <= cnt && nr <= S / w; ++ nr ) {
for (int s = S; s >= w; -- s ) {
if (dp[s - w] != -1)
dp[s] = max(dp[s], dp[s - w] + 1LL * V[ind].value);
}
-- V[ind].copies;
if (V[ind].copies == 0)
++ ind;
}
i = dr - 1;
}
LL ans = 0;
for (int i = 0; i <= S; ++ i )
ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
