#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITJ(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 2005;
int s, n;
ll ans = 0;
namespace sub5{
vector<pii> wgr[maxn];
ll dp[maxn];
void additem(ll v, int w) {
// cout << "item " << v << ' ' << w << "\n";
for (int i = s-w; i >= 0; i--) {
maximize(dp[i+w], dp[i]+v);
}
// for (int i = 0; i <= s; i++) {
// cout << i << ' ' << dp[i] << "\n";
// }
}
void consbit(int v, int w, int k) {
int sum;
for (sum = 1; sum*2-1 <= k; sum <<= 1) {
additem((ll)v*sum, w*sum);
if (k-(sum*2-1) < sum*2) break;
}
int val = k-(sum*2-1);
if (val > 0) {
additem((ll)v*val, w*val);
}
}
void solve() {
for (int i = 1; i <= n; i++) {
//pushback {v, k}
int v, w, k;
cin >> v >> w >> k;
if (w > s) continue;
if (w == s) {
maximize(ans, (ll)v);
continue;
}
wgr[w].pb({v, k});
}
memset(dp, 0, sizeof(dp));
for (int w = 1; w < s; w++) {
//consider wgr w
int sumw = 0; //only before full
sort(wgr[w].begin(), wgr[w].end(), greater<>());
for (int i = 0; i < (int)wgr[w].size(); i++) {
int v = wgr[w][i].fi, k = wgr[w][i].se;
minimize(k, (s-sumw)/w);
if (k <= 0) break;
//solve
consbit(v, w, k);
// for (int j = 1; j <= k; j++) {
// additem(v, w);
// }
//another break
sumw += k*w;
if ((s-sumw)/w <= 0) break;
}
}
for (int i = 0; i <= s; i++) {
maximize(ans, dp[i]);
}
cout << ans;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
cin >> s >> n;
// if (n == 1) return sub1::solve(), 0;
return sub5::solve(), 0;
}
/*
6 1
8 1 7
48
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
20 3
5000 15 1
100 1 3
50 1 4
*/
