#include <bits/stdc++.h>
#define int long long
using namespace std;
#define MAXN 100005
#define MAXS 2005
struct dovat{
int x, y, z;
};
vector<dovat> v;
vector<pair<int, int>> chia[MAXS];
int n, s;
int dp[MAXS];
int DP[MAXS];
void solve(){
cin >> s >> n;
for (int i = 1; i <= n; ++i){
int x, y, z; cin >> x >> y >> z;
v.push_back({x, y, z});
chia[y].emplace_back(x, z);
}
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
for (int i = 0; i <= s; ++i){
sort(chia[i].begin(), chia[i].end(), greater<pair<int,int>>());
for (int j = 0; j <= s; ++j) DP[j] = dp[j];
int W = 0;
int V = 0;
for (pair<int,int> &x : chia[i]){
while (x.second > 0 && W < s){
x.second--;
W += i;
V += x.first;
for (int j = s; j >= W; --j){
dp[j] = max(dp[j], DP[j - W] + V);
}
}
}
}
int res = 0;
for (int i = 0; i <= s; ++i){
res = max(res, dp[i]);
}
cout << res;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
