#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, int> pill;
typedef vector<pill> vpill;
typedef vector<vpill> vvpill;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
const ll inf = 1e18;
int main()
{
//freopen("..\\io\\input.txt", "r", stdin);
//freopen("..\\io\\output.txt", "w", stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);
int s, n; cin >> s >> n;
vll k(n+1, 0);
vll v(n+1, 0);
vll w(n+1, 0);
vvpll dp(n+1, vpll(s+1, {0, 0}));
for(int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i] >> k[i];
}
for(int i = 1; i <= n; i++)
{
for(int m = 0; m < w[i]; m++)
{
priority_queue<pll> pq;
for(int l = 0; m+l*w[i] <= s; l++)
{
pq.push({dp[i-1][m+w[i]*l].first - l*v[i], l});
while(l - pq.top().second > k[i])
pq.pop();
dp[i][m+w[i]*l] = max(dp[i][m+w[i]*l], {(ll)(pq.top().first + l*v[i]), (ll)(l - pq.top().second)});
}
}
}
pll ans = {0,0};
for(int i = 0; i <= s; i++)
{
ans = max(ans, dp[n][i]);
}
cout << ans.first << "\n";
}
