#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
/*--------------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-----------------*/
int main(){
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n,w;
cin>>w>>n;
//vector<vector<bool>>dp(n+1,vector<bool>(w+1,ff));
vl dp(w+1,0);
multiset <pair<ll, ll>> k;
for(int i=0; i < n; i++){
int a, b, c;
cin>>a>>b>>c;
while(c--) k.insert( {b, a} );
}
dp[0] = 0;
ll ans = 0;
for(auto i:k){
for(int j = w; j >= i.first; j--){
if(j-i.first>=0)
dsmax(dp[j], dp[j - i.first] + i.second);
//cout<<j<<' '<<i.second<<' '<<dp[j]<<endl;
}
}
cout<<*max_element (dp.begin(), dp.end())<<endl;
return 0;
}
