#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX_N = 1e5 + 5;
ll knapsack(ll n, ll maxWeight, ll weights[], ll values[], ll quantities[]) {
vector<ll> dp(maxWeight + 1, 0);
for (ll i = 1; i <= n; i++) {
if (weights[i] > maxWeight) continue;
for (ll mod = 0; mod < weights[i]; mod++) {
deque<pair<ll, ll>> dq;
for (ll w = mod; w <= maxWeight; w += weights[i]) {
ll idx = w / weights[i];
ll currVal = dp[w] - idx * values[i];
while (!dq.empty() && dq.back().first <= currVal) dq.pop_back();
dq.emplace_back(currVal, w);
if (!dq.empty() && dq.front().second < w - quantities[i] * weights[i]) dq.pop_front();
dp[w] = dq.front().first + idx * values[i];
}
}
}
return dp[maxWeight];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, maxWeight, weights[MAX_N], values[MAX_N], quantities[MAX_N];
cin >> maxWeight >> n;
for (ll i = 1; i <= n; i++) cin >> values[i] >> weights[i] >> quantities[i];
cout << knapsack(n, maxWeight, weights, values, quantities) << "\n";
return 0;
}
