#include <iostream>
using namespace std;
#define int long long
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];
signed 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]);
}
}
}
}
