#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<ll>> items(S + 1);
for (int i = 0; i < N; ++i) {
ll V, W, K;
cin >> V >> W >> K;
K = min(K, S / W);
for (int x = 1; x <= K; K -= x, x *= 2) {
items.push_back({x * V, x * W});
items[x * W].push_back(x * V);
}
if (K > 0) items[K * W].push_back(K * V);
}
vector<ll> dp(S + 1, 0);
for (int w = 1; w <= S; ++w) {
sort(rall(items[w]));
items[w].resize(min((ll)size(items[w]), S / w));
for (auto x : items[w]) {
for (ll z = S - w; z >= 0; --z) {
dp[z + w] = max(dp[z + w], dp[z] + x);
}
}
}
ll ans = *max_element(all(dp));
cout << ans << endl;
exit(0);
}
