#include <bits/stdc++.h>
using namespace std;
struct Item {
long long value;
int weight;
long long qty;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int capacity, numItems;
cin >> capacity >> numItems;
vector<priority_queue<pair<long long, long long>>> grouped(capacity + 1);
for (int i = 0; i < numItems; i++) {
Item item;
cin >> item.value >> item.weight >> item.qty;
grouped[item.weight].push(make_pair(item.value, item.qty));
}
vector<long long> dp(capacity + 1, 0);
for (int w = 1; w <= capacity; w++) {
long long maxCanTake = capacity / w;
while (!grouped[w].empty() && maxCanTake > 0) {
pair<long long, long long> topItem = grouped[w].top();
grouped[w].pop();
long long value = topItem.first;
long long qty = topItem.second;
if (qty > maxCanTake) qty = maxCanTake;
maxCanTake -= qty;
for (int i = 0; i < qty; i++) {
for (int c = capacity; c >= w; c--) {
dp[c] = max(dp[c], dp[c - w] + value);
}
}
}
}
long long answer = 0;
for (int c = 1; c <= capacity; c++) {
answer = max(answer, dp[c]);
}
cout << answer << "\n";
return 0;
}
