#include<bits/stdc++.h>
using namespace std;
const int MAX = 2005;
struct Item{
int v, w, k;
bool operator<(Item &other){
if(w == other.w)return v > other.v;
return w < other.w;
}
};
long long dp[MAX][MAX];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 0;i < MAX;++i){
for(int j = 0;j < MAX;++j){
dp[i][j] = -1e18;
}
}
dp[0][0] = 0;
int n, S;
cin >> S >> n;
vector<Item>vv(n);
for(int i = 0;i < n;++i){
int v, w, k;
cin >> v >> w >> k;
vv[i] = {v, w, k};
}
sort(vv.begin(), vv.end());
vector<vector<int>>items(S + 1);
for(int i = 0;i < n;++i){
int v = vv[i].v, w = vv[i].w, k = vv[i].k;
for(int j = 0;j < min(k, S / w) && (int)items[w].size() + 1 <= S / w;++j){
items[w].push_back(v);
}
}
for(int i = 1;i <= S;++i){
for(int j = 0;j <= S;++j){
long long sum = 0;
dp[i][j] = dp[i - 1][j];
for(int k = 0;k < (int)items[i].size() && j - (k + 1) * i >= 0;++k){
sum += items[i][k];
dp[i][j] = max(dp[i][j], dp[i - 1][j - (k + 1) * i] + sum);
}
}
}
long long mx = 0;
for(int i = 1;i <= S;++i){
mx = max(mx, dp[S][i]);
}
cout << mx << '\n';
}
