#include <bits/stdc++.h>
using namespace std;
const int MAX_S = 2005;
long long dp[MAX_S];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
fill(dp, dp + S + 1, -1);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
int w, v, k;
cin >> w >> v >> k;
// Cập nhật DP ngược với số lượng tối đa k
for (int s = S; s >= w; --s) {
if (dp[s - w] != -1) {
for (int cnt = 1; cnt <= k && s >= cnt * w; ++cnt) {
if (dp[s - cnt * w] != -1) {
dp[s] = max(dp[s], dp[s - cnt * w] + cnt * v);
}
}
}
}
}
long long max_value = *max_element(dp, dp + S + 1);
cout << max_value << endl;
return 0;
}
