#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define pll pair<ll,ll>
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update>
using ll=long long;
#define in insert
#define pb push_back
struct Node{
ll v;
ll w;
ll k;
bool operator<(const Node &other){
return w<other.w;
}
};
void solve(){
ll n,s;
cin>>s>>n;
vector<Node>v(n);
ll u,w,k;
for(int i=0;i<n;i++){
cin>>u>>w>>k;
v[i]={u,w,k};
}
vector<ll>dp(s+1,-1);
dp[0]=0;
for(Node &n:v){
for(ll x=s;x>=n.w;x--){
if(dp[x-n.w]!=-1 && n.k>0 && dp[x]<dp[x-n.w]+n.v){
dp[x]=dp[x-n.w]+n.v;
}
}
}
ll ans=0;
for(int i=s-1;i>=0;i--){
ans=max(ans,dp[i]);
}
cout<<ans;
}
int main(){
solve();
return 0;
}
