/*____________________________________________________________
// started : 07/13/22
// finished:
// problem : https://oj.uz/problem/view/NOI18_knapsack and file:///C:/Users/jayse/Downloads/statement_en.pdf
____________________________________________________________*/
#include <bits/stdc++.h>
#define FOR(n) for (int i = 0;i < n;i++)
#define FORO(n) for (int i = 1;i < n;i++)
#define ROF(n) for (int i = n - 1;i >= 0;i--)
#define ROFO(n) for (int i = n - 1;i >= 1;i--)
#define loop while (true) // rust woooo
#define ALL(arr) arr.begin(), arr.end()
#define lower lower_bound
#define upper upper_bound
#define ll long long
#define uint unsigned int
#define hashmap unordered_map
#define hashset unordered_set
#define p_queue priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define endl "\n"
#define BIG_NUMBER 1e18
#define BIG_PRIME 999998727899999 // this number has 15 digits
#define PRIME32 1e9 + 7
#define ASCII_PRIME 257
#define ALPHA_PRIME 29
using namespace std;
struct DP {
ll val;
// the weight of the previous item that we landed on the dp state with, the
// index of the item in the vector, the number of specific items already
// bought
int weight, wI, cnt;
DP() {
val = -1;
}
DP(ll val, int weight, int wI, int cnt) {
this->val = val;
this->weight = weight;
this->wI = wI;
this->cnt = cnt;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// maxWeight is S from the problem statement, can't use s as variable name
// because macro though
int maxWeight, n; cin >> maxWeight >> n;
// key -> weight, e.f -> val, e.s -> cnt. Sorted in descending order
map<int, vector<pair<int, int>>, greater<int>> items;
FOR(n) {
int val, weight, cnt; cin >> val >> weight >> cnt;
if (weight <= maxWeight) {
items[weight].pb({ val, cnt });
}
}
vector<DP> dp(maxWeight + 1);
for (auto& curr : items) {
sort(ALL(curr.s), greater<pair<int, int>>());
dp[curr.f] = DP(curr.s[0].f, curr.f, 0, 1);
}
FOR(maxWeight + 1) {
if (dp[i].val == -1) {
continue;
}
// transition
bool isStart = true;
for (auto j = items.find(dp[i].weight);j != items.end();j++) {
int newWeight = i + j->f;
if (newWeight > maxWeight) {
// can't add this item, try a lighter item
isStart = false;
continue;
}
if (isStart) {
isStart = false;
if (dp[i].cnt == j->s[dp[i].wI].s) {
// all of this particular item is taken
if (dp[i].wI < j->s.size() - 1) {
// there are still items of this particular weight left
ll newVal = dp[i].val + j->s[dp[i].wI + 1].f;
if (newVal > dp[newWeight].val && j->f >= dp[newWeight].weight) {
dp[newWeight] = DP(newVal, j->f, dp[i].wI + 1, 1);
}
}
}
else {
ll newVal = dp[i].val + j->s[dp[i].wI].f;
if (newVal > dp[newWeight].val) {
dp[newWeight] = DP(newVal, j->f, dp[i].wI, dp[i].cnt + 1);
}
}
}
else {
ll newVal = dp[i].val + j->s[0].f;
if (newVal > dp[newWeight].val) {
dp[newWeight] = DP(newVal, j->f, 0, 1);
}
}
}
}
ll ans = 0;
FOR(maxWeight + 1) {
ans = max(ans, dp[i].val);
}
cout << ans;
return 0;
}
