#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <ctype.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnof(x,y) ((x)^(1<<y))
#define oo 1000000000000000000
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())
const int mod=1e9+7;
const int base = 317;
const int Base = 100000;
using namespace std;
int n, S;
vector<ii>e[2005];
int dp[2005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> S >> n;
for(int i = 1; i <= n; i++) {
int v, w, k;
cin >> v >> w >> k;
ii tmp;
tmp.fi = v, tmp.se = k;
e[w].pb(tmp);
}
for(int w = 1; w <= S; w++) {
if(e[w].size()) {
sort(all(e[w]));
int cnt = S / w;
//cout << e[w][0].fi << "\n";
for(int vt = e[w].size() - 1; vt >= 0; vt--) {
int V = e[w][vt].fi;
//cout << V << "\n";
if(cnt > e[w][vt].se) {
cnt -= e[w][vt].se;
for(int i = 1; i <= e[w][vt].se; i++) {
for(int j = S; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + V);
}
}
}
else {
for(int i = 1; i <= cnt; i++) {
for(int j = S; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + V);
}
}
break;
}
}
}
}
cout << dp[S];
}
// ProTeam
//(¯`·.·´¯) (¯`·.·´¯)
//`·.¸(¯`·.·´¯)¸ .·
//×°× ` ·.¸.·´ ×°×
