#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Item pair<ll, ll>
#define ItemList vector<Item>
const ll mod=998244353;
const ll MAX_CAP=2007;
const ll MAX_ITEMS=1e5+7;
ll values[MAX_ITEMS], weights[MAX_ITEMS], quantities[MAX_ITEMS];
void solve(){
ll S, N; cin>>S>>N;
ll max_quantity=0;
for (int i=0; i<N; i++) {
cin>>values[i]>>weights[i]>>quantities[i];
max_quantity=max(max_quantity, quantities[i]);
}
ll dp[MAX_CAP];
memset(dp, 0, sizeof(dp));
ItemList items_by_weight[MAX_CAP];
for (ll i=0; i<N; i++){
items_by_weight[weights[i]].push_back({values[i], quantities[i]});
}
for (ll w=1; w<MAX_CAP; w++){
if(items_by_weight[w].empty()) continue;
sort(items_by_weight[w].rbegin(), items_by_weight[w].rend());
ll current_item_idx = 0;
for (ll i=0; i<S/w; i++){
if(current_item_idx>=items_by_weight[w].size()) break;
ll current_value=items_by_weight[w][current_item_idx].first;
for (ll capacity=S; capacity>=w; capacity--){
dp[capacity]=max(dp[capacity], dp[capacity-w]+current_value);
}
items_by_weight[w][current_item_idx].second--;
if (items_by_weight[w][current_item_idx].second==0) {
current_item_idx++;
}
}
}
cout << dp[S] << '\n';
return;
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
// precomputation
//
const bool multitest=false;
if(multitest){
ll t; cin>>t;
while(t--){
solve();
}
} else {
solve();
}
return 0;
}
