#include "bits/extc++.h"
using namespace std;
#ifdef LOCAL
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif
#define inf 1000000000
#define llinf 1000000000000000000ll
#define uset unordered_set
#define umap unordered_map
#define mp(a,b) make_pair(a,b)
#define mt(x...) make_tuple(x)
#define eb(x...) emplace_back(x)
#define pb(x) push_back(x)
#define ff first
#define ss second
const char el = '\n', sp = ' ';
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
template<class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int S = 2005;
int s, n, dp[S];
vii v[S];
void fun(int a, int c){
for(int i = s; i >= c; --i)
dp[i] = max(dp[i], dp[i-c] + a);
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("debug.txt", "w", stderr);
#endif
cin >> s >> n;
while(n--){
int a, c, k;
cin >> a >> c >> k;
v[c].eb(a, k);
}
for(int i = 1; i <= s; ++i){
sort(v[i].begin(), v[i].end(), greater<>());
int cur = 0;
for(auto [a, k]: v[i]){
if(cur>s/i)
break;
while(cur<=s/i&&k>0){
fun(a, i);
--k;
++cur;
}
}
}
cout << dp[s];
}
