#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1; // Number of test cases
while (t--) {
int x, n;
cin >> x >> n; // Maximum weight capacity and number of items
vector<vector<int>> arr(n, vector<int>(3)); // Item details: value, weight, max quantity
for (int i = 0; i < n; i++) {
cin >> arr[i][0]; // Value of item
cin >> arr[i][1]; // Weight of item
cin >> arr[i][2]; // Maximum quantity of item
}
vector<int> dp(x + 1, 0); // DP array to store max profit for each capacity
// Process each item
for (int i = 0; i < n; i++) {
int value = arr[i][0];
int weight = arr[i][1];
int maxQuantity = arr[i][2];
// Process for bounded quantity
for (int capacity = x; capacity >= weight; capacity--) {
for (int quantity = 1; quantity <= maxQuantity && quantity * weight <= capacity; quantity++) {
dp[capacity] = max(dp[capacity], quantity * value + dp[capacity - quantity * weight]);
}
}
}
cout << dp[x] << "\n"; // Maximum profit for capacity x
}
return 0;
}
