#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct couple{
ll v,k;
};
struct item{
ll v,w;
};
bool comp(couple a, couple b){
return a.v > b.v;
}
ll n,s,w,v,k,limit,counting;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>s>>n;
vector<couple> kkk[2010];
vector<ll> dp(s+1, 0);
vector<item> potential_items;
for(int i=0; i<n; i++){
cin>>v>>w>>k;
if(w <= s){
kkk[w].push_back({v,k});
}
}
for(int i=1; i<=s; i++){
if(kkk[i].empty()) continue;
sort(kkk[i].begin(), kkk[i].end(), comp);
limit = s/i;
counting = 0;
for(auto item:kkk[i]){
ll v = item.v;
ll k = item.k;
ll limit_taking;
limit_taking = min(k, limit-counting);
for(int j=0; j<limit_taking; j++){
potential_items.push_back({v,i});
}
counting += limit_taking;
if(counting == limit) break;
}
}
for(int i=0; i<potential_items.size(); i++){
for(int j=s; j>=potential_items[i].w; j--)
dp[j] = max(dp[j], dp[j-potential_items[i].w] + potential_items[i].v);
}
cout<<dp[s];
}
//ý tưởng: cho (v,k) của các món hàng có cùng trọng lượng vào 1 vector
//mỗi món hàng có w[i] có thể lấy tối đa là s/w[i] số lượng
//sort những món hàng có cùng trọng lượng lại, sau đó lấy hết (không quá limit_taking) lượng món có v cao nhất
