#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 last = 0;
for(int x = 0; x < n; x++)
{
int v, w, k; cin >> v >> w >> k;
for(int y = 1; y <= k; y++)
{
if(w*y + last > s) break;
pro[w*y + last] = true;
dp[w*y + last] = dp[last] + v*y;
}
for(int z = s; z >= 0; z--)
{
while(w*k > z) k--;
if(pro[z - w*k]) {
pro[z] = true;
last = max(last, z);
}
dp[z] = max(dp[z], dp[z - w*k] + v*k);
}
/*for(int y = 1; y <= k; y++)
{
for(int z = s; z >= 0; z--)
{
if(z - w < 0) continue;
dp[z] = max(dp[z], dp[z - w] + v);
mx = max(mx, dp[z]);
}
//cout << mx << " ";
}*/
}
int mx = 0;
for(int x = 0; x < s; x++)
{
if(pro[x]) 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;
}
