#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair <ll, ll>
#define foru(i,a,b) for (ll i = a; i <= b; i++)
#define ford(i,a,b) for (ll i = a; i >= b; i--)
#define N int(1e5 + 5)
#define M int(2e3 + 5)
#define MOD int(1e9 + 7)
#define base 311
int n, s;
ll dp[M];
vector <ll> w[M];
bool cmp(int i, int j)
{
return i > j;
}
int main()
{
//freopen("KNAPSACK.inp","r",stdin);
// freopen("KNAPSACK.out","w",stdout);
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> s >> n;
foru(i, 1, n)
{
int v, u, k;
cin >> v >> u >> k;
while (k--) w[u].push_back(v);
}
foru(i, 1, s)
{
dp[i] = -1;
sort(w[i].begin(), w[i].end(), cmp);
}
foru(i, 1, s)
foru(j, 0, min((ll)w[i].size(), s/i) - 1)
ford(z, s, i)
if (dp[z - i] != -1)
dp[z] = max(dp[z], dp[z - i] + w[i][j]);
cout << *max_element(dp, dp+1+s);
return 0;
}
