#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;
struct korek {
int l, e, k;
};
korek arr[100004];
int val[100004][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);
for(int i = 1; i <= arr[idx].k; i++) {
if(weight-i*arr[idx].e >= 0) ret = max(ret, ks(idx+1, weight-i*arr[idx].e)+i*arr[idx].l);
else break;
}
return val[idx][weight] = ret;
}
signed main() {
ioss;
memset(val, -1, sizeof(val));
cin >> t >> n;
for(int i = 0; i < n; i++) cin >> arr[i].l >> arr[i].e >> arr[i].k;
int ans = ks(0, t);
cout << ans << endl;
}
