#include <bits/stdc++.h>
using namespace std;
#define num long long
const int MAX_S = 2002;
struct Object {
int W, V, K;
Object () = default;
void scan () {
cin >> V >> W >> K;
}
bool operator< (const Object &other) const {
return V > other.V;
}
};
struct ElementArray {
vector<Object> objects;
void _sort () {
sort(objects.begin(), objects.end());
}
void iterate (int max_iter, void (*f)(int, int)) {
int idx = 0;
for (Object obj : objects) {
for (int k = 0; k < obj.K; k ++) {
f(obj.W, obj.V);
idx ++;
if (idx >= max_iter) return ;
}
}
}
};
ElementArray objects[MAX_S];
void create () {
Object obj;
obj.scan();
objects[obj.W].objects.push_back(obj);
}
num dp[MAX_S];
void apply (int weight, int value) {
for (int idx = MAX_S - 1 - weight; idx >= 0; idx --)
dp[idx + weight] = max(dp[idx + weight], dp[idx] + value);
}
int main () {
int S, N;
cin >> S >> N;
for (int idx = 0; idx < N; idx ++) create();
for (int idx = 0; idx <= S; idx ++) objects[idx]._sort();
for (int idx = 0; idx <= S; idx ++)
objects[idx].iterate(S, apply);
cout << dp[S];
}
