//Name: Nguyen Quang Huy
//Time: 2023-2024
#include <bits/stdc++.h>
#define Foru(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define se second
#define fi first
#define nl cout << "\n";
#define pi pair<int,int>
#define bit(x, k) (1ll&((x)>>(k)))
#define sz size
#define io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ms(a,i) memset(a,i,sizeof(a))
#define pb(x) push_back(x)
#define epb(x,y) emplace_back({x,y})
#define all(x) (x).begin(), (x).end()
#define hr cout << "-----------------------------------------------\n";
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;
template<class T> T mi(T a, T b){return (a<=b)?a:b;}
template<class T> T ma(T a, T b){return (a>=b)?a:b;}
template<class T> void Unique(vector<T> &v){sort(all(v));v.erase(unique(all(v)), v.end());}
struct Item{
int w,v,k;
} items[maxn];
int n,s;
ll dp[maxn];
void ioFile(string str){
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
}
void inp(){
cin >> s >> n;
Foru(i,1,n){
cin >> items[i].v >> items[i].w >> items[i].k;
}
}
void solve(){
vector<pi> tmp[2001];
Foru(i,1,n){
tmp[items[i].w].push_back({items[i].v,items[i].k});
}
Foru(i,1,s){
if(tmp[i].empty())continue;
sort(all(tmp[i]));
int id=0;
Foru(j,1,s/i){
if(id>=tmp[i].sz())break;
Ford(k,s,1)if(k>=i){
dp[k]=max(dp[k],dp[k-i]+tmp[i][id].fi);
}
tmp[i][id].se--;
if(tmp[i][id].se==0)++id;
}
}
cout << dp[s];
}
int main(){
io();
inp();
solve();
return 0;
}
