#include <bits/stdc++.h>
#define ll long long
using namespace std;
int V[100005] = {}, W[100005] = {}, K[100005] = {};
int DP[2][2005] = {};
int solve(int N, int S) {
for (int i = 0; i <= S; i++) {
DP[0][i] = min(i/W[1], K[1]) * V[1];
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= S; j++) {
int mx = 0;
for (int k = 0; k <= K[i] && k*W[i] <= j; k++)
mx = max(mx, DP[0][j - k*W[i]] + k*V[i]);
DP[1][j] = mx;
}
swap(DP[0], DP[1]);
}
return DP[0][S];
}
int main() {
memset(DP, -1, sizeof DP);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int S, N;
cin >> S >> N;
for (int i = 1; i <= N; i++) {
cin >> V[i] >> W[i] >> K[i];
K[i] = min(K[i], 2000);
}
cout << solve(N, S) << '\n';
return 0;
}
