#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a, b) for (int i = a; i < b; i++)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL << 60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll, pair<ll, ll>>
#define goog(tno) cout << "Case #" << tno << ": "
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
#define read(x) \
int x; \
cin >> x
using namespace std;
int main()
{
fast_io;
int t = 1;
// cin >> t;
while (t--)
{
int s, n;
cin >> s >> n;
ll v[n], w[n], k[n];
fr(0, n) cin >> v[i] >> w[i] >> k[i];
ll dp[s + 1];
dp[0] = 0;
memset(dp, 0, sizeof dp);
fr(0, n)
{
for (int j = s; j >= 0; j--)
{
rep(r, 1, k[i] + 1)
{
if (j + r * w[i] > s)
break;
dp[j + r * w[i]] = max(dp[j] + r * v[i], dp[j + r * w[i]]);
}
}
}
ll res = 0;
// for (int i = 0; i < s; i++)
// cout << dp[i] << " ";
// // fr(0, s + 1)
// // {
// // cout << dp[i] << " ";
// // }
fr(0, s + 1) res = max(res, dp[i]);
cout << res;
}
return 0;
}
