#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ull unsigned long long
#define ll long long
#define SPEED \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
const int N = 1000 + 13;
const int maxa = 1e6 + 13;
const ll mod = 998244353;
using tp = tuple<ll, ll, ll>;
void prestart() {}
ll dp[maxa];
void start()
{
int s, n;
cin >> s >> n;
vector<tp> a;
forn(i, n) {
ll v, w, k;
cin >> v;
cin >> w;
cin >> k;
a.push_back({v, w, k});
}
sort(a.begin(), a.end(), [](tp a, tp b) {
ll f = get<0>(a) * get<1>(b);
ll m = get<0>(b) * get<1>(a);
if (f == m) return get<1>(b) > get<1>(a);
return get<0>(a) * get<1>(b) > get<0>(b) * get<1>(a);
});
// cout << "\n";
// for(auto i : a) {
// cout << get<0>(i) << " " << get<1>(i) << " " << get<2>(i) << "\n";
// }
for (int i = 0; i < n; i++)
{
ll v = get<0>(a[i]);
ll w = get<1>(a[i]);
ll k = get<2>(a[i]);
for (int j = s; j >= 0; j--)
{
ll l = min(k, j / w);
dp[j] = max(dp[j], dp[j - w * l] + v * l);
}
}
cout << dp[s] << "\n";
}
signed main()
{
SPEED;
int t = 1;
prestart();
// cin >> t;
while (t--)
{
start();
}
}
