#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) {
int bit[30] = {};
for(int i = 0; i <= 29; i++) {
bit[i] = (n >> i) & 1;
}
int msb = -1;
for(int i = 29; i >= 0; i--) {
if(bit[i]) {
msb = i;break;
}
}
if(msb == -1)return {};
function<void(int)> do_work = [&](int i) {
if(!bit[i + 1])do_work(i + 1);
bit[i + 1]--;
return bit[i] = 2, void();
};
for(int i = 0; i < msb; i++) {
if(!bit[i]) {
do_work(i);
}
}
vector<int>res;
for(int i = 0; i <= 29; i++) {
while(bit[i] > 0) {
res.push_back(1 << i);bit[i]--;
}
}
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;
vector<int>vec = execute(k);
for(auto &x : vec) {
a.push_back({w * x, v * x});
}
}
n = (int)a.size();
vector dp(2, vector<int>(s + 1, -1));
for(int j = 0; j <= s; j++)dp[n & 1][j] = 0;
for(int i = n - 1; i >= 0; i--) {
for(int j = 0; j <= s; j++) {
int skip = dp[(i + 1) & 1][j];
int take = 0;
if(j >= a[i].first)take = a[i].second + dp[(i + 1) & 1][j - a[i].first];
dp[i & 1][j] = max(take, skip);
}
}
cout << dp[0][s] << '\n';
return 0;
}
