#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define int long long
#define inf 1'000'000'000'000
using namespace std;
typedef priority_queue<pair<long long, long long>> prq;
priority_queue<pair<int, int>> vpq[2001];
int dp[2005];
int32_t main()
{
int s, n;
cin >> s >> n;
for (int i = 0; i < n; i++)
{
int v, w, k;
cin >> v >> w >> k;
vpq[w].push({v, k});
}
// floyd-warshall
for (int i = 1; i <= s; i++)
{
int mx = s/i;
while (!vpq[i].empty() && mx)
{
pair<int, int> pr = vpq[i].top();
vpq[i].pop();
pr.second = min(pr.second, mx);
for (int j = 0; j < pr.second; j++)
for (int z = s; z >= i; z--)
dp[z] = max(dp[z], dp[z-i] + pr.first);
mx -= pr.second;
}
}
int rez = 0;
for (int i = 0; i <= s; i++)
rez = max(rez, dp[i]);
cout << rez << "\n";
return 0;
}
