/* Author: Serpentx
Noob here xD */
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define vi vector<int>
#define vvi vector <vi>
#define NO { cout << "NO" << endl; return; }
#define YES {cout << "YES" << endl; return; }
#define print(v) for(auto &it:v) cout << it << ' '
const int MOD = 1e9+7;
const int INF = LLONG_MAX >> 1;
void solve() {
int S, n ;
cin >> S >> n;
vi arr(n), brr(n), crr(n);
for(int i=0;i<n;i++){
cin >> arr[i] >> brr[i] >> crr[i];
}
vvi dp(n,vi(S+1,0));
// dp[i][j] = maximum profit using i , weight using j
dp[0][0]=0;
for(int i=0;i<n;i++){
dp[i][0]=0;
}
for(int i=1;i<n;i++){
for(int j=0;j<=S;j++){
int value = arr[i];
int weight = brr[i];
if(j-weight>=0){
dp[i][j] = max(dp[i][j], max(value+dp[i-1][j-weight],dp[i-1][j]));
}
else{
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
}
}
cout << dp[n-1][S] << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
