#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 w[N], v[N], k[N], dp[M], tmp[M];
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) cin >> v[i] >> w[i] >> k[i];
foru(i, 1, s) dp[i] = -1;
foru(i, 1, n)
{
foru(j, 1, s) tmp[j] = 0;
foru(j, w[i], s)
{
if (dp[j - w[i]] == -1) continue;
if (dp[j] < dp[j - w[i]] + v[i] && tmp[j - w[i]] < k[i])
{
dp[j] = dp[j - w[i]] + v[i];
tmp[j] = tmp[j - w[i]] + 1;
}
}
}
cout << *max_element(dp, dp+1+s);
return 0;
}
