#include <bits/stdc++.h>
using namespace std;
int knapsack(int W, vector<int> &val, vector<int> &wt) {
int n = wt.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
int pick = 0;
if (wt[i - 1] <= j)
pick = val[i - 1] + dp[i - 1][j - wt[i - 1]];
int notPick = dp[i - 1][j];
dp[i][j] = max(pick, notPick);
}
}
return dp[n][W];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, s;
cin >> s >> n;
vector<int> w, v;
for (int i = 0; i < n; i++) {
int vi, wi, ki;
cin >> vi >> wi >> ki;
int k = 1;
while (ki >= k) {
w.push_back(wi * k);
v.push_back(vi * k);
ki -= k;
k <<= 1;
}
if (ki > 0) {
w.push_back(wi * ki);
v.push_back(vi * ki);
}
}
cout << knapsack(s, v, w);
return 0;
}
