#include <bits/stdc++.h>
using namespace std;
struct Item {
long long v , w , k;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S , N;
cin >> S >> N;
vector<Item> a(N);
for (int i = 0 ; i < N ; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
a[i].k = min(a[i].k , S * 1LL);
}
const long long inf = (long long)1e18;
auto Get_candidates = [&](int val) {
vector<long long> c;
for (int i = 30 ; i >= 0 ; i--) {
long long cur = (1LL << i);
if (cur <= val) {
c.push_back(cur);
c.push_back(val - (cur - 1));
c.push_back(val - cur);
}
}
return c;
};
vector<vector<long long>> dp(N , vector<long long> (S + 1 , -1));
function<long long(int , long long)> Solve = [&](int id , long long cur) {
if (cur < 0) return -inf;
if (id == N) return 0LL;
auto &p = dp[id][cur];
if (p != -1) return p;
long long ans = -inf;
vector<long long> c = Get_candidates(a[id].k);
for (int i = 0 ; i < (int)c.size() ; i++) {
assert(c[i] <= a[id].k);
long long cost = a[id].w * c[i];
long long add = a[id].v * c[i];
ans = max(ans , Solve(id + 1 , cur - cost) + add);
}
ans = max(ans , Solve(id + 1 , cur));
return p = ans;
};
cout << Solve(0 , S) << '\n';
return 0;
}
