#include <bits/stdc++.h>
#define endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
if(y == 0) return 1 ;
if(y == 1) return x ;
ll ret = mypower(x , y / 2);
ret = (ret * ret) % mod;
if(y % 2) ret = ( ret * x ) % mod ;
return ret ;
}
ll to , n , dp[2001][101] ;
ll wa[200009] , v[200009] , k[200009] ;
ll sol(ll ind , ll rem){
if(rem < 0){
return -1e18 ;
}
if(ind > n){
return 0 ;
}
ll &ret = dp[rem][ind] ;
if(ret != -1){
return ret ;
}
return ret = max(sol(ind + 1 , rem) , sol(ind + 1 , rem - wa[ind]) + v[ind]) ;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> to >> n ;
for(int i = 1 ; i <= n ; i++){
cin >> v[i] >> wa[i] >> k[i] ;
}
memset(dp , -1 , sizeof dp) ;
ll ans = sol(1 , to) ;
cout << ans << endl ;
return 0 ;
}
