#include <bits/stdc++.h>
using namespace std;
struct Item {
int V, W, K;
Item() {
V = 0;
W = 0;
K = 0;
}
Item(int v, int w, int k) {
V = v;
W = w;
K = k;
}
bool operator< (Item other) {
if (W != other.W) return W < other.W;
return V < other.V;
}
};
bool comp(Item i1, Item i2) {
double rat1 = (i1.V * 1.0)/i1.W;
double rat2 = (i2.V * 1.0)/i2.W;
if (abs(rat1 - rat2) > 1e-9) {
return rat1 > rat2;
}
return i1.V > i2.V;
}
int main() {
int S, N;
cin >> S >> N;
Item items[N];
for (int i = 0; i < N; i++) {
cin >> items[i].V >> items[i].W >> items[i].K;
items[i].K = min(items[i].K, S/items[i].W);
}
sort(items, items + N);
vector<pair<int, int>> itemList[S + 1];
int ind = 0;
int curW, delW;
for (int w = 1; w <= S; w++) {
itemList[w].clear();
curW = 0;
while (ind < N && items[ind].W == w && curW < S) {
delW = min(items[ind].K, S - curW);
itemList[w].push_back({delW, items[ind].V});
curW += delW;
ind++;
}
}
int dp[S + 1];
fill(dp, dp + S + 1, 0);
vector<Item> decVal;
for (int w = 1; w <= S; w++) {
for (pair<int, int> p : itemList[w]) decVal.push_back(Item(p.second, w, p.first));
}
sort(decVal.begin(), decVal.end(), comp);
for (Item i : decVal) {
for (int k = 0; k < i.K; k++) {
for (int w = S - i.W; w >= 0; w--) {
dp[w + i.W] = max(dp[w + i.W], dp[w] + i.V);
}
}
}
cout << *max_element(dp, dp + S + 1) << "\n";
return 0;
}
