#include <bits/stdc++.h>
using namespace std;
const int MAXS = 2005, MAXN = 1e5 + 5;
const long long inf = 1e18 + 3;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numVal, lim, val[MAXN], weight[MAXN], num[MAXN], used[MAXS];
long long dp[MAXS];
void input(){
cin >> lim >> numVal;
for(int i = 1; i <= numVal; i++) cin >> val[i] >> weight[i] >> num[i];
}
void solve(){
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
for(int i = 1; i <= numVal; i++){
for(int j = 0; j <= lim; j++) used[j] = 0;
for(int j = 0; j + weight[i] <= lim; j++) if (dp[j] > -inf){
if (used[j] < num[i]){
if (maximize(dp[j + weight[i]], dp[j] + val[i]))
used[j + weight[i]] = used[j] + 1;
}
}
}
long long res = -inf;
for(int i = 0; i <= lim; i++) maximize(res, dp[i]);
cout << res << '\n';
}
int main(){
input();
solve();
}
