#include <bits/stdc++.h>
using namespace std;
int main() {
int S, N;
cin >> S >> N;
long long v[N + 1], w[N + 1], k[N + 1];
long long dp[S + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= N; i++) cin >> v[i] >> w[i] >> k[i];
for (int i = 1; i <= N; i++) {
long long upperK = S / w[i];
upperK = min(upperK, k[i]);
//binary splitting
for (long long j = 1; upperK > 0; j <<= 1) {
long long tmp = min(j, upperK);
long long weight = tmp * w[i];
long long value = tmp * v[i];
for (int s = S; s >= weight; s--) {
dp[s] = max(dp[s - weight] + value, dp[s]);
}
upperK -= tmp;
}
}
cout << dp[S] << endl;
}
