#include <bits/stdc++.h>
using namespace std;
/*
_ ____ ____ ____
/ \/ _\/ __\/ _\
| || / | \/|| /
| || \__| __/| \__
\_/\____/\_/ \____/
*/
#define mask(x) (1 << x)
#define all(x) x.begin(), x.end()
#define int long long
/* FUNCTIONS */
void ckmax(int &a, int b) { a = max(a, b); }
void ckmin(int &a, int b) { a = min(a, b); }
int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b); }
int lcm(int a, int b) { return a/gcd(a,b)*b; }
struct item{int v, w, k;};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
while (t--)
{
// code here
int s, n; cin >> s >> n;
vector<item> a(n);
int sum = 0;
for (int i=0; i<n; i++)
{
cin >> a[i].v >> a[i].w >> a[i].k;
sum += a[i].w;
}
vector<int> dp(s + 1, 0); // giá trị lớn nhất với trọng lượng là i sao cho tổng <= s
int ans = 0;
for (int i=0; i<n; i++)
{
for (int j=1; j<=a[i].k; j+=1)
{
for (int W=s; W>=a[i].w; W-=1)
{
ckmax(dp[W], dp[W - a[i].w] + a[i].v);
}
}
}
for (int i=0; i<=s; i++)
{
ckmax(ans, dp[i]);
}
cout << ans << endl;
}
return 0;
}
