//https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
const int maxs = 2000;
const int maxv = 1000000;
int n;
long long s, v[maxn+5], w[maxn+5], k[maxn+5], dp[maxs+5];
void read() {
cin >> s >> n;
for (int i = 1; i<=n; ++i) cin >> v[i] >> w[i] >> k[i];
}
void sub1() { //N = 1
cout << v[1] * (min(k[1], s / w[1]));
}
void sub2() { //1<=N<=100 && K[1] = 1 ---> Knapsack 0/1
long long res = 0;
for (int item = 1; item <= n; ++item) {
for (int sum = s; sum > 0; --sum) {
if (sum < w[item]) continue;
dp[sum] = max(dp[sum - w[item]] + v[item], dp[sum]);
}
}
for (int sum = 1; sum <= s; ++sum) {
res = max(res, dp[sum]);
}
cout << res;
}
void sub3() { //1<=N<=100 && 1<=k[i]<=10 ---> Bounded Knapsack
long long res = 0;
for (int item = 1; item <= n; ++item) {
for (int sum = s; sum > 0; --sum) {
if (sum < w[item]) continue;
for (int take = 1; take <= k[item]; ++take) {
if (take * w[item] > sum) break;
dp[sum] = max(dp[sum - take*w[item]] + take*v[item], dp[sum]);
}
}
}
for (int sum = 1; sum <= s; ++sum) {
res = max(res, dp[sum]);
}
cout << res;
}
void sub4() { //1<=N<=100 && 1<=k[i]<=1e9
vector <long long> W, V;
for (int i = 1; i<=n; ++i) {
long long cnt = k[i];
long long base = 1;
while (cnt > 0) {
long long take = min(base, cnt);
W.push_back(w[i]*take);
V.push_back(v[i]*take);
cnt -= take;
base <<= 1;
}
}
for (int i = 0; i < W.size(); ++i) {
for (int sum = s; sum >= W[i]; --sum) {
dp[sum] = max(dp[sum], dp[sum - W[i]] + V[i]);
}
}
cout << dp[s];
}
void sub5() {
}
void solve() {
int g = *max_element(k+1, k+n+1);
if (g == 1) {
sub2();
return;
}
if (n == 1) sub1();
else if (1 <= n && n <= 100 && g == 1) sub2();
else if (1 <= n && n <= 100 && g <= 10) sub3();
else if (1 <= n && n <= 100 && g <= 1e9) sub4();
// else sub5();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
read();
solve();
return 0;
}
