#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;
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.push_back({w * x, v * x});
}
}
n = (int)a.size();
vector dp(n, vector<int>(s + 1, -1));
function<int(int, int)> solve = [&](int i,int left) {
if(i == n)return 0ll;
int &ans = dp[i][left];
if(~ans)return ans;
ans = solve(i + 1, left);
if(left >= a[i].first)ans = max(ans, a[i].second + solve(i + 1, left - a[i].first));
return ans;
};
cout << solve(0, s) << '\n';
return 0;
}
