#include<bits/stdc++.h>
using namespace std;
#define int long long
int s, n;
struct Cake{
int v, w, k;
};
Cake cake[100003];
int memo[100003][2003];
int binser(int l, int r, int we, int idx){
if(l > r){
return 0;
}
if(idx == n + 1){
return 0;
}
int &res = memo[idx][we];
if(res != -1) return res;
int ans = binser(0, cake[idx + 1].k, we, idx + 1);
int mid = (l+r)/2;
int val = mid * cake[idx].w;
if(val <= we) ans = max(ans, cake[idx].v*mid + binser(0, cake[idx + 1].k, we - cake[idx].w*mid, idx + 1));
ans = max(ans, max(binser(l, mid - 1, we, idx), binser(mid + 1, r, we, idx)));
return res = ans;
}
signed main(){
memset(memo, -1, sizeof memo);
cin >> s >> n;
for(int i = 1; i<=n; i++){
int x, y, z;
cin >> x >> y >> z;
cake[i].v = x;
cake[i].w = y;
cake[i].k = z;
}
cout << binser(0, cake[1].k, s, 1);
}
