#include <bits/stdc++.h>
#define int long long
using namespace std;
#define f first
#define s second
typedef pair<int,int> pii;
typedef tuple<int, int, int> iii;
int mod = (int)1e9 + 7;
int lt(int l, int r, function<bool(int x)> f)
{
l--;
while(l < r)
{
int m = l + (r - l + 1) / 2;
if(f(m)) r = m;
else l = m + 1;
}
return l;
}
int pw(int a, int b)
{
int ans = 1;
while(b > 0)
{
if(b & 1) ans *= a;
ans %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ans;
}
int inverse(int x)
{
return pw(x, mod - 2);
}
void solve()
{
int s, n; cin >> s >> n;
int dp[s + 1] = {0};
bool pro[s + 1] = {false};
pro[0] = true;
int mp[2001];
for(int x = 1; x < 2001; x++) mp[x] = s/x;
vector<pii> choose;
vector<iii> a;
for(int x = 0; x < n; x++)
{
int v, w, k; cin >> v >> w >> k;
a.push_back({v, w, k});
}
sort(a.rbegin(), a.rend());
for(iii t : a)
{
int v = get<0>(t);
int w = get<1>(t);
int k = get<2>(t);
if(mp[w] >= k)
{
for(int x = 0; x < k; x++) choose.push_back({v, w});
mp[w] -= k;
}
else
{
for(int x = 0; x < mp[w]; x++) choose.push_back({v, w});
mp[w] = 0;
}
}
int mx = 0;
for(pii p : choose)
{
//cout << p.f << " " << p.s << "\n";
for(int x = s; x >= 0; x--)
{
if(x - p.s >= 0)
{
if(pro[x - p.s])
{
pro[x] = true;
dp[x] = max(dp[x], dp[x - p.s] + p.f);
mx = max(mx, dp[x]);
}
}
}
}
cout << mx;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
//freopen("wormsort.in", "r", stdin);
//freopen("wormsort.out", "w", stdout);
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
return 0;
}
