#include<bits/stdc++.h>
using namespace std;
#define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int t, n;
int l[104], e[104], k[104], val[104][2004];
int ks(int idx, int weight) {
if(idx == n) return 0;
if(weight <= 0) return 0;
if(val[idx][weight] != -1) return val[idx][weight];
int ret = ks(idx+1, weight);
if(weight-e[idx] >= 0) ret = max(ret, ks(idx+1, weight-e[idx])+l[idx]);
return val[idx][weight] = ret;
}
signed main() {
ioss;
memset(val, -1, sizeof(val));
cin >> t >> n;
for(int i = 0; i < n; i++) cin >> l[i] >> e[i] >> k[i];
int ans = ks(0, t);
cout << ans << endl;
}
