#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (ll i = a; i < b; i++)
#define fr(i, a, b) for (ll i = b - 1; i >= a; i--)
#define fx(i, a, b, x) for (ll i = a; i < b; i += x)
#define fa(x) for (auto ele : x)
#define fav(tmp, x) for (auto tmp : x)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppiii pair<pair<int, int>, int>
#define p(e1, e2) pair<e1, e2>
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define v(ele) vector<ele>
#define sei set<int>
#define sel set<ll>
#define ses set<string>
#define sec set<char>
#define se(ele) set<ele>
#define mii map<int, int>
#define mll map<ll, ll>
#define mp(e1, e2) map<e1, e2>
#define mcpci map<char, pair<char, int>>
#define mic map<int, char>
#define mci map<char, int>
#define mcsei map<char, sei>
#define mcvi map<char, vi>
#define mci map<char, int>
#define msi map<string, int>
#define qi queue<int>
#define ql queue<ll>
#define qpii queue<pair<int, int>>
const ll mod = 1e9 + 7;
const ll INF = 1e16;
const ll NEG_INF = LONG_LONG_MIN;
const ll N = 2e5 + 20;
// const int N = 11;
ll knapsack(v(vl) vec, ll s)
{
ll n = vec.size();
v(vl) dp(n, vl(s + 1));
f(i, 0, n)
{
dp[i][0] = 0;
}
f(j, vec[0][0], s + 1)
{
dp[0][j] = vec[0][1];
}
f(i, 1, n)
{
f(j, 1, s + 1)
{
if (j - vec[i][0] >= 0)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j - vec[i][0]] + vec[i][1]);
}
if (i > 0)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
}
return dp[n - 1][s];
}
void solve()
{
ll s, n;
cin >> s >> n;
v(vl) arr;
f(i, 0, n)
{
ll v, w, k;
cin >> v >> w >> k;
if (w <= s)
{
arr.push_back({v, w, k});
}
}
v(vl) vec;
vl cnt(2001);
f(i, 1, 2001)
{
cnt[i] = s / i;
}
sort(all(arr), greater_equal<vl>());
fa(arr)
{
f(i, 0, min({ele[2], cnt[ele[1]]}))
{
vec.push_back({ele[1], ele[0]});
cnt[ele[2]]--;
}
}
cout << knapsack(vec, s) << '\n';
return;
}
void sig_handler(int signum)
{
printf("Inside handler function\n");
exit(0);
}
int main()
{
time_t begin, end;
time(&begin);
// signal(SIGALRM, sig_handler);
// alarm(2);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
time(&end);
time_t elapsed = end - begin;
// printf("Time measured: %ld seconds.\n", elapsed);
return 0;
}
