#include<bits/stdc++.h>
using namespace std;
int t[2005][2005];
int knapsack(int s, int n, vector<int>& V, vector<int>& W, vector<int>& K) {
// we have 2 choices
// Base case -- smallest possible input
if(n == 0 || s == 0) return 0;
if(t[n][s] != -1) return t[n][s];
if (W[n - 1] > s) return t[n][s] = knapsack(s, n - 1, V, W, K);
int ans = knapsack(s, n-1, V, W, K);
for(int i=1;i<=K[n-1];i++) {
if(i*W[n-1] <= s) {
// we have choices
ans = max(i*V[n-1] + knapsack(s-i*W[n-1], n-1, V, W, K), ans);
} else break;
}
return t[n][s] = ans;
}
int main() {
int S; // capacity
int N;
cin>>S >>N;
vector<int> V(N);
vector<int> W(N);
vector<int> K(N); // it is copies
for(int i=0;i<N;i++) {
cin>>V[i] >>W[i]>>K[i];
}
// now , we have to return
cout<< knapsack(S, N, V, W, K) <<endl;
}
