#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N lli(2e5)
#define MOD lli(1e9 + 7)
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef vector<plli> vplli;
typedef pair<lli, plli> pplli;
typedef vector<pplli> vpplli;
lli n,m,k,q,t;
vlli vect;
lli dp[N];
int main()
{
fast_io
cin >> m >> n;
for(lli i = 0;i<n;i++){
cin >> q >> t >> k;
for(lli j = 0;j<=29;j++){
lli su = 1<<j;
if(k >= su){
k-=su;
lli suag = su * t;
lli sudeg = su * q;
for(lli z = m - suag;z>=0;z--){
if(z == 0){
dp[z + suag] = max(dp[z+suag], sudeg);
continue;
}
if(dp[z] <= 0)
continue;
dp[z + suag] = max(dp[z + suag], dp[z] + sudeg);
}
}else
break;
}
if(k > 0){
lli suag = k * t;
lli sudeg = k * q;
for(lli z = m - suag;z>=0;z--){
if(z == 0){
dp[z + suag] = max(dp[z+suag], sudeg);
continue;
}
if(dp[z] <= 0)
continue;
dp[z + suag] = max(dp[z + suag], dp[z] + sudeg);
}
}
}
lli cev = 0;
for(lli i = 0;i<=m;i++){
cev = max(cev, dp[i]);
}
cout << cev << endl;
}
