#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S, N;
cin >> S >> N;
vector<pair<int, int>> obj;
for (int i = 0; i < N; i++) {
int val, wt, copies;
cin >> val >> wt >> copies;
for (int p = 1; copies; p <<= 1) {
int take = min(p, copies);
obj.emplace_back(take * wt, take * val);
copies -= take;
}
}
int M = obj.size();
vector<vector<int>> dp(M + 1, vector<int>(S + 1, 0));
for (int i = 1; i <= M; i++) {
auto [wt, val] = obj[i - 1];
for (int cap = 0; cap <= S; cap++) {
dp[i][cap] = dp[i - 1][cap];
if (cap >= wt)
dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - wt] + val);
}
}
cout << *max_element(dp[M].begin(), dp[M].end()) << "\n";
return 0;
}
