#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define pb push_back
#define mp make_pair
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n,m;
cin >> n >> m;
vector<pair<long long, long long>> pq;
long long dp[n + 1];
if(m != 1){
for(long long i = 0; i <= n; i++){
dp[i] = 0;
}
}
bool is = 0;
if(m == 1){
is = 1;
}
long long ans1 = 0;
vector<long long> q(m);
for(long long i = 0; i < m; i++){
long long a,b,c;
cin >> a >> b >> c;
q[i] = n / b;
c = min(c, q[i]);
ans1 = max(ans1, c);
pq.push_back({a, b});
if(!is){
while(c > 1){
pq.push_back({a, b});
c--;
}
long long u = pq.size();
}
// for(long long k = n; k >= a; k--){
// dp[k] = max(dp[k], dp[k - a] + b);
// }
}
long long tt = 0;
if(m == 1){
cout << min((n / pq[0].ss), ans1) * pq[0].ff;
}
else{
long long y = pq.size();
for(int i = 0; i < y; i++){
for(long long k = n; k >= pq[i].ss; k--){
dp[k] = max(dp[k], dp[k - pq[i].ss] + pq[i].ff);
}
}
long long ans = 0;
for(int i = 0; i <= n; i++){
ans = max(ans, dp[i]);
}
cout << ans;
}
}
