#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include <numeric>
#include <map>
#include <bit>
#include <fstream>
#include <functional>
#include <array>
#include <chrono>
// #include<bits/stdc++.h>
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
using namespace std;
struct pair_hash {
inline std::size_t operator()(const std::pair<int, int>& v) const {
return v.first * 31 + v.second;
}
}; // for unordered set of pairs
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
#define rep(i, a, n) for(int i = a; i < n; ++i)
#define exists(s, e) (s.find(e) != s.end())
#define def_sort(s) (sort(s.begin(), s.end()))
#define def_reverse(s) (sort(s.rbegin(), s.rend()))
#define lsone(s) (s & -s)
#define endl '\n'
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
const long long INF = 1LL << 62;
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 }; // first 4 for urdl rest for diags
int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
ll MOD = 1e9 + 7;
int rows, cols;
bool ok(int i, int j) {
return (i >= 0 && j >= 0 && i < rows && j < cols);
}
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
ull read_int() {
bool minus = false;
ull result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch - '0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result * 10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
template <typename T>
T mod(T a, T b = 1) {
T rez = a % b;
if (rez < 0)
rez += b;
return rez;
}
void add(ll& a, ll b) {
a += b;
if (a >= MOD) a -= MOD;
}
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
void solve() {
int n, s; cin >> s >> n;
//group on weights
map<int,vector<pair<int,int>>>weights;
for(int i = 0; i < n;++i)
{
int v,w,k;cin >> v>>w>>k;
if(w <= s)
weights[w].push_back({v,k});
}
int dp[2][s+1];
int prev = 0;
int curr = 1;
memset(dp,0,sizeof(dp));
for(auto &[w,item] : weights)
{
//always make sense to take higher value elements for same weight first
sort(item.rbegin(),item.rend());
for(int i = 1; i <= s; ++i)
{
int val = 0;
int curr_item = -1;
int wt_cnt = 0;
int tmp = 0;
while (i - wt_cnt*w >= 0)
{
if(tmp == 0)
{
curr_item++;
if(curr_item == item.size())break;
tmp = item[curr_item].second;
continue;
}
val += item[curr_item].first;
wt_cnt++;
tmp--;
if(i - wt_cnt*w >= 0)
{
dp[curr][i] = max({dp[prev][i],dp[prev][i - wt_cnt*w]+val,dp[curr][i]});
}
}
}
curr^=1;
prev^=1;
}
curr^=1;
int res = 0;
for(int i = 0; i <= s; ++i){res = max(res,dp[curr][i]);}
cout << res<< endl;
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0);
// freopen("div7.in", "r", stdin);
// freopen("div7.out", "w", stdout);
// cout << setprecision(50);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
cerr << "Time elapsed:" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
