// vegnim
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define setpre(n) fixed << setprecision(n)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mask(n) (1LL << (n))
#define getbit(x, b) (((x) >> (b)) & 1)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define task ""
#define dbg if (DEBUG_MODE)
const bool DEBUG_MODE = 0;
const int maxN = 1e5+5, maxS = 2005;
int s,n,v[maxN],w[maxN],k[maxN];
namespace sub1
{
void solve()
{
ll ans = 0;
while (k[1]-- && s - w[1] >= 0){
ans += v[1];
s -= w[1];
}
cout << ans;
}
}
namespace sub2
{
const int maxN = 105;
int dp[maxN][maxS];
void solve()
{
FOR(i, 1, n){
FOR(j, 0, s){
dp[i][j] = dp[i-1][j];
if (j >= w[i]) dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
}
}
cout << dp[n][s];
}
}
namespace sub3
{
const int maxN = 1e3+5;
int dp[maxN][maxS];
void solve()
{
int m = n;
FOR(i, 1, n){
REP(j, k[i]-1){
m++;
v[m] = v[i];
w[m] = w[i];
}
}
n = m;
FOR(i, 1, n){
FOR(j, 0, s){
dp[i][j] = dp[i-1][j];
if (j >= w[i]) dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
}
}
cout << dp[n][s];
}
}
namespace sub4
{
const int maxN = 4000;
ll wt[maxN],val[maxN],dp[maxN][maxS];
void solve()
{
int m = 0;
FOR(i, 1, n){
for (int j=0; (1 << j) <= k[i]; j++){
m++;
wt[m] = (1LL << j) * w[i];
val[m] = (1LL << j) * v[i];
k[i] -= (1 << j);
}
if (k[i]){
m++;
wt[m] = 1LL*k[i] * w[i];
val[m] = 1LL*k[i] * v[i];
}
}
n = m;
FOR(i, 1, n){
FOR(j, 0, s){
dp[i][j] = dp[i-1][j];
if (j >= wt[i]) dp[i][j] = max(dp[i][j], val[i] + dp[i-1][j-wt[i]]);
}
}
cout << dp[n][s];
}
}
namespace sub5
{
vector<vector<pii>> item;
ll dp[maxS][maxS];
void solve()
{
item.assign(s+1, vector<pii> {});
FOR(i, 1, n){
item[w[i]].pb({v[i], k[i]});
}
FOR(i, 1, s){
sort(all(item[i]), greater<pii>());
}
dbg{
FOR(i, 1, s){
if (item[i].empty()) continue;
cout << i<<": ";
for (auto x : item[i]){
cout << x.fi<<','<<x.se<<' ';
}
cout<<'\n';
}
}
FOR(i, 1, s){
FOR(j, 0, s){
dbg cout << "?? "<<i<<','<<j<<'\n';
dp[i][j] = dp[i-1][j];
ll sumval = 0;
int sumw = 0;
int p = 0, itemcnt = 0;
while (p < sz(item[i])){
if (item[i][p].se - itemcnt <= 0){
p++;
itemcnt = 0;
continue;
}
if (j < sumw + i){
break;
}
sumw += i;
sumval += item[i][p].fi;
itemcnt++;
dp[i][j] = max(dp[i][j], sumval + dp[i-1][j - sumw]);
dbg cout << "update with val "<<sumval<<" at "<<i<<','<<j<<" w "<<sumw<<'\n';
}
}
}
dbg{
cout << dp[1][1]<<'\n';
}
cout << dp[s][s];
}
}
signed main()
{
ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
// freopen("inp.txt","r",stdin);
cin >> s >> n;
bool issub2 = (n <= 100);
bool issub3 = (n <= 100);
bool issub4 = (n <= 100);
FOR(i, 1, n){
cin >> v[i] >> w[i] >> k[i];
if (k[i] != 1) issub2 = 0;
if (k[i] > 10) issub3 = 0;
}
if (n == 1){
sub1::solve();
return 0;
}
if (issub2){
sub2::solve();
return 0;
}
if (issub3){
sub3::solve();
return 0;
}
if (issub4){
sub4::solve();
return 0;
}
sub5::solve();
return 0;
}
