#include "bits/stdc++.h"
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll S;
int N;
cin >> S >> N;
vector<vector<array<ll, 2>>> items(S + 1);
for (int i = 0; i < N; ++i) {
ll V, W, K;
cin >> V >> W >> K;
items[W].push_back({V, K});
}
vector<ll> dp(S + 1, 0);
auto insert = [&](ll V, ll W) {
for (ll x = S - W; x >= 0; --x) {
dp[x + W] = max(dp[x + W], dp[x] + V);
}
};
for (ll W = 1; W <= S; ++W) {
sort(rall(items[W]));
ll left = S / W;
for (auto [V, K] : items[W]) {
if (left == 0) break;
K = min(K, left);
left -= K;
for (int x = 1; x <= K; K -= x, x *= 2) insert(x * V, x * W);
if (K > 0) insert(K * V, K * W);
}
}
ll ans = *max_element(all(dp));
cout << ans << endl;
exit(0);
}
