#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define testcases int tt;cin >> tt;while(tt--)
template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
vector<int> execute(int n) {
vector<int>res;
int curr = 1;
while(n) {
res.push_back(curr);
n -= curr;
curr <<= 1;
if(curr > n)curr = n;
}
return res;
}
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int s, n;cin >> s >> n;
vector<pair<int, int>>a(n * 30);int idx = 0;
for(int i = 0; i < n; i++) {
int v, w, k;cin >> v >> w >> k;
k = min(k, (s + w - 1) / w);
vector<int>vec = execute(k);
for(auto &x : vec) {
a[idx++] = {w * x, v * x};
}
}
n = (int)a.size();
vector dp(2, vector<int>(s + 1, -1));
for(int i = 0; i <= s; i++)dp[n & 1][i] = 0;
for(int i = n - 1; i >= 0; i--) {
for(int j = 0; j <= s; j++) {
dp[i & 1][j] = dp[!(i & 1)][j];
if(j >= a[i].first)dp[i & 1][j] = max(dp[i & 1][j], dp[!(i & 1)][j - a[i].first] + a[i].second);
}
}
cout << dp[0][s] << '\n';
return 0;
}
