#include<bits/stdc++.h>
const int maxn=100005;
long variables[maxn][4];
int V;
void helper (long cost,long val){
for(long i=V;i>=cost;i--) {
variables[i][3]=std::max(variables[i][3],variables[i-cost][3] + val);
}
return ;
}
int main() {
std::ios::sync_with_stdio(false);
int n;
std::cin>>V>>n; // knapsack size, n kinds of items
for(int i=1;i<=n;i++) {
std::cin>>variables[i][1]>>variables[i][0]>>variables[i][2]; // weight, value, quantity
}
for(int i=1;i<=n;i++) {
long k=1;
while(k<variables[i][2]){
helper(k * variables[i][0], k * variables[i][1]);
variables[i][2]-=k;
k*=2;
}
helper(variables[i][2]*variables[i][0],variables[i][2]*variables[i][1]);
}
std::cout<<variables[V][3]<<'\n';
}
