#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int s, n;
cin >> s >> n;
vector<int> v(n);
vector<int> w(n);
vector<int> k(n);
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
}
vector<vector<int>> dp(n + 1, vector<int>(s + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= s; j++) {
for (int c = 0; c <= k[i - 1]; c++) {
if (j - c * w[i - 1] < 0)break;
dp[i][j] = max(dp[i][j], dp[i - 1][j - c * w[i - 1]] + c * v[i - 1]);
}
}
}
int ans = 0;
for (int i = 0; i <= s; i++) {
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
}
