#include <bits/stdc++.h>
using namespace std;
// Constants
const int MAX_N = 1e5 + 5; // Maximum number of items
// Function to calculate the maximum value
int knapsack(int n, int maxWeight, int weights[], int values[], int quantities[]) {
vector<int> dp(maxWeight + 1, 0); // DP array for max value with given weight
for (int i = 1; i <= n; i++) {
int weight = weights[i];
int value = values[i];
int quantity = quantities[i];
if (weight > maxWeight) continue; // Skip items heavier than the capacity
// Modular optimization to handle bounded knapsack
for (int mod = 0; mod < weight; mod++) {
deque<pair<int, int>> dq; // Stores pairs of (value, weight)
for (int currentWeight = mod; currentWeight <= maxWeight; currentWeight += weight) {
int index = currentWeight / weight;
int 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];
}
int weights[MAX_N], values[MAX_N], quantities[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int maxWeight, n;
cin >> maxWeight >> n;
for (int i = 1; i <= n; i++) {
cin >> values[i] >> weights[i] >> quantities[i];
}
cout << knapsack(n, maxWeight, weights, values, quantities) << "\n";
return 0;
}
