#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Constants
const ll MAX_N = 1e5 + 5; // Maximum number of items
// Function to calculate the maximum value
ll knapsack(ll n, ll maxWeight, ll weights[], ll values[], ll quantities[]) {
vector<ll> dp(maxWeight + 1, 0); // DP array for max value with given weight
for (ll i = 1; i <= n; i++) {
ll weight = weights[i];
ll value = values[i];
ll quantity = quantities[i];
if (weight > maxWeight) continue; // Skip items heavier than the capacity
// Modular optimization to handle bounded knapsack
for (ll mod = 0; mod < weight; mod++) {
deque<pair<ll, ll>> dq; // Stores pairs of (value, weight)
for (ll currentWeight = mod; currentWeight <= maxWeight; currentWeight += weight) {
ll index = currentWeight / weight;
ll currentValue = dp[currentWeight] - index * value;
// Maintain deque: Remove elements that are not optimal
while (!dq.empty() && dq.back().first <= currentValue)
dq.pop_back();
dq.emplace_back(currentValue, currentWeight);
// Remove elements that exceed the quantity constraint
if (!dq.empty() && dq.front().second < currentWeight - quantity * weight)
dq.pop_front();
// Update DP with the maximum value
dp[currentWeight] = dq.front().first + index * value;
}
}
}
return dp[maxWeight];
}
ll weights[MAX_N], values[MAX_N], quantities[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll maxWeight, 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;
}
