#include <bits/stdc++.h>
using namespace std;
#define M 2005
#define fi first
#define se second
#define log 11
typedef pair<int, int> ii;
int dp[M], n, s, pw[log + 5];
vector<ii> sov[M];
vector<ii> g;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
pw[0] = 1;
for (int i = 1; i <= log; i++) pw[i] = pw[i - 1] * 2;
cin >> s >> n;
for (int i = 1; i <= n; i++){
int w, v, k;
cin >> v >> w >> k;
sov[w].push_back({v, k});
}
for (int i = 1; i <= s; i++){
sort(sov[i].begin(), sov[i].end(), greater<ii>());
int gt = s;
for (auto x : sov[i]){
int v = x.fi, k = x.se;
k = min(k, gt / i);
int d = -1;
while (pw[d + 1] * i <= gt && pw[d + 1] <= k && gt > 0){
k -= pw[d + 1];
gt -= pw[d + 1] * i;
d++;
g.push_back({pw[d] * i, pw[d] * v});
}
if (k > 0) {
k = min(k, gt / i);
gt -= k * i;
if (k > 0)
g.push_back({k * i, k * v});
}
}
}
int res = 0;
for (auto x : g){
int w = x.fi;
int v = x.se;
for (int j = s; j >= 0; j--){
if (j >= w) dp[j] = max(dp[j], dp[j - w] + v);
res = max(res, dp[j]);
}
}
cout << res;
return 0;
}
