#include <iostream>
using namespace std;
void Knapsack(int n,int W);
int N = 100000, MaxW = 20;
int w[100000+1]; // w???
int v[100000+1]; // v???
int num[100000+1]; // num??
int dp[100000+1];
int main(){
cin >> MaxW >> N;
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i] >> num[i];
}
Knapsack(N, MaxW);
cout << dp[MaxW];
}
void Knapsack(int n,int W){
for(int i=1;i<=n;i++){ // ??????
for(int k=0;k<num[i];k++){ // ???????num[i]?
for(int j=W;j>0;j--){ // ????????
if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
// ????
//for(int j=0; j<=W; j++){cout << dp[j] << " ";}
//cout << "\n";
}
}
}
