#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
using namespace std;
#define Shahriyor ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vp vector<pair<int,int>>
#define vvi vector<vi>
#define vvs vector<vs>
#define vvc vector<vc>
#define vvp vector<vector<pair<int,int>>>
#define vvvi vector<vector<vector<int>>>
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define endl '\n'
#define len(a) (int)(a).length()
#define sz(a) (int)(a).size()
#define inf LLONG_MAX
#define no { cout << "NO\n"; return; }
#define yes cout << "YES\n";
#define zero { cout << "0\n"; return; }
#define impossible { cout << "-1\n"; return; }
#define IMPOSSIBLE { cout << "IMPOSSIBLE\n"; return; }
const int mod = 1e9+7;
string directions = "URDL";
vi dx = {-1, 0, 1, 0};
vi dy = {0, 1, 0, -1};
void file_io() {
freopen("i.txt", "r", stdin);
freopen("o.txt", "w", stdout);
}
istream& operator>>(istream& in, vp& a) {
for (auto& p : a) in >> p.first >> p.second;
return in;
}
ostream& operator<<(ostream& out, vp& a) {
for (auto& p : a) out << p.first << " " << p.second << '\n';
return out;
}
ostream& operator<<(ostream& out, vi& a) {
for (int i = 0; a.size() > i; i++) out << a[i] << ' ';
return out;
}
istream& operator>>(istream& in, vi& a) {
for (int i = 0; a.size() > i; i++) in >> a[i];
return in;
}
int lcm(int x,int y){
return x*y / __gcd(x,y);
}
int sqrt(int n) {
int m = max((int) 0, (int) sqrtl(n) - 10);
while ((m+1) * (m+1) <= n) m++;
return m;
}
int sum(vi& l) {
return accumulate(all(l), 0LL);
}
int log(int n, int x) {
int c = 0;
while(n > 1){
n /= x;
c++;
}
return c;
}
string bin(int x,int k){
string s = "";
do{
s = char(x % k + 48) + s;
x /= k;
}while(x);
return s;
}
struct DSU {
vi parent; int count;
DSU(int n) : parent(n+1), count(n) {
for (int i = 1; i <= n; i++) parent[i] = i;
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool merge(int x, int y) {
int a = find(x), b = find(y);
if (a == b) return false;
parent[b] = a;
count--;
return true;
}
};
void Solve();
signed main(signed argc, char *argv[]) {
Shahriyor;
if (argc > 1 && string(argv[1]) == "gg") file_io();
int t = 1;
// cin >> t;
while(t--) Solve();
}
void dfs(int idx,vi used,vi& dp,vvi& l){
for(int i=0;i<sz(l);i++){
if(idx+l[i][1]<sz(dp)){
if(used[i]+1<=l[i][2] && dp[idx]+l[i][0]>=dp[idx+l[i][1]]){
used[i]++;
dp[idx+l[i][1]]=dp[idx]+l[i][0];
dfs(idx+l[i][1],used,dp,l);
used[i]--;
}
}
}
}
void Solve(){
int s,n;
cin>>s>>n;
vvi l(n,vi(3));
for(int i=0;i<n;i++) cin>>l[i];
vi dp(s+2,-1);
dp[0]=0;
vi used(n,0);
dfs(0,used,dp,l);
int ans=0;
for(int i=1;i<=s;i++) ans=max(ans,dp[i]);
cout << ans << endl;
}
