#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int S, N;
cin >> S >> N;
vector<tuple<int, int, int>> items; // (value, weight, count)
for (int i = 0; i < N; i++) {
int V, W, K;
cin >> V >> W >> K;
items.push_back({V, W, K});
}
// dp[w] = maximum value possible with weight w
vector<long long> dp(S + 1, 0);
for (auto [value, weight, count] : items) {
// Skip items that are too heavy
if (weight > S) continue;
// Process from right to left to avoid using the same item multiple times
for (int w = S; w >= weight; w--) {
// Try using j copies of current item
for (int j = 1; j <= count && j * weight <= w; j++) {
dp[w] = max(dp[w], dp[w - j * weight] + j * (long long)value);
}
}
}
cout << dp[S] << endl;
return 0;
}
