/*
* @Author: Twynzz
* @Last Modified by: Twynzz
* @Note For This Problem: https://wbd.ms/share/v2/aHR0cHM6Ly93aGl0ZWJvYXJkLm1pY3Jvc29mdC5jb20vYXBpL3YxLjAvd2hpdGVib2FyZHMvcmVkZWVtL2Y3ZTc5NDk0NDFhNzRkNjA5NTg5MDZkNjc1NDAzNmJlX0JCQTcxNzYyLTEyRTAtNDJFMS1CMzI0LTVCMTMxRjQyNEUzRF9iZDE4OGRiZC0yMDRlLTQ0MmItYTg4Yy03YWM5MDhlY2U4ZTA=
*/
#include <bits/stdc++.h>
using namespace std;
char __ST__;
extern char __EN__;
// ------------ Define ------------
#define int long long
#define ll long long
#define ld long double
#define str string
#define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
#define IOS {std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define _TBN_ signed main()
#define setp(n) setprecision(n)<< fixed
#define fi first
#define se second
#define ii pair<int,int>
#define gcd(a,b) __gcd(a,b)
#define iii tuple<int, int, int>
#define pb push_back
#define pf push_front
#define eb emplace_back
#define sz(v) (int)v.size()
#define el "\n"
#define all(x) x.begin(),x.end()
const long long oo = 1e18;
const int MOD = 1e9+7, Mod = 998244353;
const int base = 311, base2 = 293;
const pair<ll, ll> INVALID_ROOT = {oo, oo};
template<class X>
bool maximize(X &a, const X &b)
{
if (a<b)
{
a = b;
return 1;
}
return 0;
}
template<class X>
bool minimize(X &a, const X &b)
{
if (a>b)
{
a = b;
return 1;
}
return 0;
}
namespace sub1
{
bool checkSub1();
void sub1();
}
namespace sub2
{
bool checkSub2();
void sub2();
}
namespace sub3
{
bool checkSub3();
void sub3();
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
int sqr(int x) {return x*x;}
inline bool MASK(int mask, int bit) {return ((mask >> bit) & 1);}
inline long long F(int n) {return n * (n + 1) / 2;}
inline int add(int a, int b, int m = MOD)
{
return ((a % m + b % m) % m + m) % m;
}
inline int sub(int a, int b, int m = MOD)
{
return ((a % m - b % m) % m + m) % m;
}
inline int mul(int a, int b, int m = MOD)
{
return (((a % m) * (b % m)) % m + m) % m;
}
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
const int maxn = 1e6 + 9;
const int N = 5e4 + 6;
// ------------ Code ------------
int s, n, v[maxn], w[maxn], k[maxn];
_TBN_
{
IOS;
if (fopen("xxx.inp","r")) file("xxx");
cin >>s >>n;
for(int i = 1; i <= n; i++) cin >>v[i] >>w[i] >>k[i];
for(int i = 1; i <= 1; i++)
{
// if (sub1::checkSub1()) {sub1::sub1(); continue;}
if (sub2::checkSub2()) {sub2::sub2(); continue;}
if (sub3::checkSub3()) {sub3::sub3(); continue;}
}
cerr << "\nStatic memory used: " << fixed << setprecision(3) << ((&__EN__ - &__ST__) / (1.0L * 1024 * 1024)) << "mb\n";
return 0;
}
namespace sub1
{
bool checkSub1()
{
return n <= 100;
}
int dp[3000];
void sub1()
{
memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; i++)
{
int rem = k[i];
for(int p = 1; rem > 0; p *= 2)
{
int cap = min(rem, p);
int cur_v = v[i] * cap, cur_w = w[i] * cap;
for(int j = s; j >= cur_w; j--)
maximize(dp[j], dp[j - cur_w] + cur_v);
rem -= cap;
}
}
cout<< *max_element(dp, dp + 1 + s)<< el;
}
}
namespace sub2
{
bool checkSub2()
{
return 1;
}
vector<ii> store[2009];
int a[maxn], b[maxn], c[maxn], m, dp[2009];
void sub2()
{
// n <= 1e5 nhung w[i] <= s <= 2000
// => co rat nhieu w[i] trung lap
// => nen cac w[i] lai
for(int i = 1; i <= n; i++)
store[w[i]].eb(v[i], k[i]);
for(int i = 1; i <= s; i++)
{
if (store[i].empty()) continue;
sort(store[i].rbegin(), store[i].rend());
int sum = 0, lim = s / i;
// worst case: toan bo n phan tu duoc phan bo dong deu tu 1 -> s
// => s/1 + s/2 + ... + s/s => m co gia tri xap xi sang uoc la s.logs
for(ii cur : store[i])
{
sum += cur.se;
m++;
a[m] = cur.fi, b[m] = i, c[m] = cur.se;
if (sum >= lim) break;
}
}
memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= m; i++)
{
int rem = c[i];
for(int p = 1; rem > 0; p *= 2)
{
int cap = min(p, rem);
int cur_v = a[i] * cap, cur_w = b[i] * cap;
for(int j = s; j >= cur_w; j--)
maximize(dp[j], dp[j - cur_w] + cur_v);
rem -= cap;
}
}
cout<< *max_element(dp, dp + 1 + s)<< el;
}
}
namespace sub3
{
bool checkSub3()
{
return 1;
}
void sub3()
{
}
}
char __EN__;
