#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;
}
};
vector<long long>dp1, dp2;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
dp1.assign(MAX, -1e18);
dp2.assign(MAX, -1e18);
dp2[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;
dp1[j] = dp2[j];
for(int k = 0;k < (int)items[i].size() && j - (k + 1) * i >= 0;++k){
sum += items[i][k];
dp1[j] = max(dp1[j], dp2[j - (k + 1) * i] + sum);
}
}
dp2 = dp1;
}
long long mx = 0;
for(int i = 1;i <= S;++i){
mx = max(mx, dp1[i]);
}
cout << mx << '\n';
}
