#include<bits/stdc++.h>
using namespace std;
#define NAME "TEST"
#define nl '\n'
#define allofa(x,sz) x+1,x+sz+1
#define allof(x) x.begin(),x.end()
#define mset(x,val) memset(x,val,sizeof(x))
template<typename T> T Max(T x, T y){return(x>y)?x:y;};
template<typename T> T Min(T x, T y){return(x<y)?x:y;};
template<class X,class Y> bool minimize(X &a, Y b){if(a>b){a=b;return true;}return false;};
template<class X,class Y> bool maximize(X &a, Y b){if(a<b){a=b;return true;}return false;};
typedef long long ll;
const ll mod = (long long)1e9+7;
const ll LINF = (long long)1e18;
const int INF = (int)1e9;
const int MAXN = (int)1e5+5;
int v[MAXN],w[MAXN],k[MAXN];
ll dp[2010];
int s,n;
void ccps() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(NAME".inp","r")) {
freopen(NAME".inp","r",stdin);
freopen(NAME".out","w",stdout);
}
}
namespace FinalSol {
struct info {
int value,weight,quantity;
info(): value(0), weight(0), quantity(0) {}
info(int V, int W, int K): value(V), weight(W), quantity(K) {}
bool operator <(const info &ot) const {
if(value!=ot.value) return value>ot.value;
if(quantity!=ot.quantity) return quantity>ot.quantity;
return weight>ot.weight;
}
};
void sol() {
vector<info> a;
for (int i = 1; i<=n; i++) {
a.push_back({v[i],w[i],k[i]});
}
vector<vector<info>> bucket(s+1);
vector<int> W;
for (const info &x : a) {
int weight = x.weight;
bucket[weight].push_back(x);
W.push_back(weight);
}
sort(allof(W));
W.resize(unique(allof(W))-W.begin());
for (int x : W) {
vector<info> &cur = bucket[x];
sort(allof(cur));
int t = 0, cnt = 0, ptr = 0;
while(t*x<=s and ptr<(int)cur.size()) {
for (int c = s; c>=x; c--) {
maximize(dp[c],dp[c-x]+cur[ptr].value);
}
t++;cnt++;
if(cnt>=cur[ptr].quantity) {
cnt = 0;
ptr++;
}
}
}
cout << dp[s];
}
}
signed main() {
ccps();
cin >> s >> n;
for (int i = 1; i<=n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
return FinalSol::sol(),0;
}
