#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "H:\code\codeforces\debug.h"
#else
#define debug(...)
#define sdebug(...)
#endif
//https://oj.uz/problem/view/NOI18_knapsack
const ll inf = (ll) 1e16;
ll dp[2][2005];
void solve() {
int capacity, n;
cin >> capacity >> n;
ll profit[n + 1], weight[n + 1], copy[n + 1];
for (int i = 1; i <= n; ++i) cin >> profit[i] >> weight[i] >> copy[i];
for (int i = 1; i <= n; ++i) {
for (int rem = 1; rem <= capacity; ++rem) {
for (ll cnt = 1; cnt <= min(copy[i], 2004LL); ++cnt) {
if (rem - (cnt * weight[i]) >= 0) dp[1][rem] = max(dp[1][rem], dp[0][rem - (cnt * weight[i])] + (profit[i] * cnt));
dp[1][rem]= max(dp[1][rem], dp[0][rem]);
}
}
for (int rem = 1; rem <= capacity; ++rem) dp[0][rem] = dp[1][rem];
}
cout << dp[1][capacity] << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}
