#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
signed main() {
int S, N; cin >> S >> N;
vector<int>V(N), W(N), K(N);
for (int i = 0; i < N; ++i) {
cin >> V[i] >> W[i] >> K[i];
K[i] = min(K[i],2000ll);
}
vector<int>dp(S+1,-1);
dp[0] = 0ll;
for (int i = 0; i < N; ++i) {
for (int k = S; k > 0; --k) {
for (int j = K[i]; j > 0; --j) {
int T = k - j*W[i];
if (T < 0ll || dp[T] == -1ll) continue;
dp[k] = max(dp[k], dp[T] + j*V[i]);
}
}
}
cout << *max_element(dp.begin(),dp.end());
}
