#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int S, N;
cin >> S >> N;
vector<pair<int, int>> items; // (weight, value)
for (int i = 0; i < N; i++) {
int V, W, K;
cin >> V >> W >> K;
// use binary representation to break down K copies
// into powers of 2 (+ remainder) to represent all possible quantities
for (int p = 1; K > 0; p *= 2) {
int take = min(p, K);
items.push_back({take * W, take * V});
K -= take;
}
}
// run 0-1 knapsack
vector<int> dp(S + 1, 0); // dp[i] = max value with max capacity i
for (auto [w, val] : items) {
if (w <= S) {
for (int j = S; j >= w; j--) { // j = capacity
dp[j] = max(dp[j], dp[j - w] + val);
}
}
}
cout << dp[S] << endl;
}
