#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int S_MAX = 100005;
ll dp[2][S_MAX];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s, n;
if (!(cin >> s >> n)) return 0;
vector<pair<ll, ll>> doVat;
for (int i = 0; i < n; i++) {
ll v_i, w_i, k_i;
cin >> v_i >> w_i >> k_i;
// Tách nhị phân chuẩn: 1, 2, 4, 8...
for (ll j = 1; k_i >= j; j <<= 1) {
doVat.push_back({j * v_i, j * w_i});
k_i -= j;
}
if (k_i > 0) {
doVat.push_back({k_i * v_i, k_i * w_i});
}
}
for (int j = 0; j <= s; j++) dp[0][j] = -1;
dp[0][0] = 0;
for (int i = 0; i < (int)doVat.size(); i++) {
int cur = i % 2;
int next = (i + 1) % 2;
ll V = doVat[i].first;
ll W = doVat[i].second;
// Reset hàng tiếp theo
for (int j = 0; j <= s; j++) dp[next][j] = -1;
for (int j = 0; j <= s; j++) {
if (dp[cur][j] == -1) continue;
dp[next][j] = max(dp[next][j], dp[cur][j]);
if (j + W <= s) {
dp[next][j + W] = max(dp[next][j + W], dp[cur][j] + V);
}
}
}
ll ans = 0;
int final_row = (int)doVat.size() % 2;
for (int j = 0; j <= s; j++) {
ans = max(ans, dp[final_row][j]);
}
cout << ans;
return 0;
}
