#pragma optimise GCC "O3" //o3 is imporant, removes unused functions
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
const ll LLMAX = 2147483648;
#define tt true
#define ff false
const int maxn = 1e5+10;
/*--------------guide-----------
* us = unsigned
* uo = unordered
* v = vector<>
* ms = multiset
* s(first) = set
* s(after) = short
* m = map
* i = int
* l = long long
* vv = vector<vector<>>
* ii = pair<int,int>
* ll = pair<long long, long long>
* sz = sets size
* vsort / rvsort = sorts a vector in ascending (vsort) or descending (rvsort) order
* tmax = max function that supports comparing two variable types
* tmin = tmax but min
* smax / smin = tmax/tmin but it sets the FIRST input to the result of the min/max
-------------------------------*/
#define us unsigned
#define vi vector <int>
#define vvi vector <vi>
#define vii vector <pair <int,int>>
#define vl vector <ll>
#define vvl vector <vl>
#define vll vector <pair <ll,ll>>
#define vvlsz(x, y) (x, vector <ll> (y))
#define vvisz(x, y) (x, vector <int>(y))
#define vvlszst(x, y, z) (x, vector <ll> (y, z))
#define vviszst(x, y, z) (x, vector <int>(y, z))
#define uosi unordered_set<int>
#define uosl unordered_set<ll>
#define si set<int>
#define sl set<ll>
#define msi multiset<int>
#define msl multiset<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mil map<int,ll>
#define mli map<ll,ii>
#define mmis map<int,short>
#define mmsi map<short,int>
#define vsort(x) sort(x.begin(), x.end())
#define rvsort(x) sort(x.rbegin(), x.rend())
#define tmax(a, b) a>b ? a:b
#define tmin(a, b) a<b ? a:b
#define smax(a, b) a = a>b ? a:b
#define smin(a, b) a = a<b ? a:b
#define dsmax(a, b) a = max(a, b)
#define dsmin(a, b) a = min(a, b)
#define qc(x) for(auto &i:x)cin>>i
/*-----------------prewritten functions-----------------*/
static inline ll tmod(ll a,ll b){
if(a>=0)return a%b;
else return b-a%b;
}
bool isprime(ll a){
if(a==2)return tt;
if(a==1||a%2==0)return ff;
for(ll i=3;i*i<=a;i+=2)if(a%i==0)return ff;
return tt;
}
class monotonicStack{
stack<int> k;
void insert(int i){
while(!k.empty() && k.top()<i)k.pop();
k.push(i);
}
inline int top(){
return k.top();
}
};
class monotonicQueue{
list<int>k;
void push(int i){
while(!k.empty() && k.back()<i)k.pop_back();
k.push_back(i);
}
inline void pop(int i){if(!k.empty() && k.front()==i)k.pop_front();}
inline int front(){return k.empty()?0:k.front();}
};
class DSU{
static int root(int x, vector<int>&k) {return k[x]<0?x:k[x]=root(k[x],k);}
bool join(int x, int y, vector<int>&k){
x=root(x,k);
y=root(y,k);
if(x==y)return 0;
k[x]+=k[y];
k[y]=x;
return true;
}
};
/*-----------------problem-specific code-----------------*/
vector<pair <int, int>> k [maxn]; // vector is faster than map; mem isnt too big of an issue
int main(){
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n,w;
cin>>w>>n;
if(n==1){
ll a,b,c;
cin>>a>>b>>c;
cout<<min(w/b,c)*a; // optimise fork
return 0;
}
//vector<vector<bool>>dp(n+1,vector<bool>(w+1,ff));
vl dp(w+1,0);
//vector <pair<ll, ll>> k;
for(int i=0; i < n; i++){
int a, b, c;
cin>>a>>b>>c;
smin(c,w/b);
k[b].push_back( {a, c});
}
dp[0] = 0;
vi kx, val;
for(int i = 1; i <= w; i++){
sort(k[i].begin(), k[i].end(), [] (pair<int, int> a, pair<int, int> b)
{return a.first > b.first;});
int cnt = 0;
for(int j = 0; j < k[i].size(); j++){
int a = k[i][j].first, b = k[i][j].second;
if(cnt * i > w) break;
for(int l = 1; l <= b;l++){
if(cnt*i>w) break;
cnt++;
kx.push_back (i);
val.push_back (a);
}
}
}
for(int i = 0; i < kx.size(); i++){
for(int s = w; s >= kx[i]; s--)
dp[s] = max(dp[s], dp[s-kx[i]] + val[i]);
}
ll ans = 0;
for(int i = 1; i <= w; i++) ans = max(ans, dp[i]);
cout<<ans;
return 0;
}
