#include <bits/stdc++.h>
using namespace std;
//policy based data structure
#include<bits/extc++.h>
using namespace __gnu_pbds;
using pii=pair<int,int>;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update
>ordered_set;
// os.find_by_order(k); iterator kth lowest element
// os.order_of_key(x); number of elements strictly less than x
// some bits operations
//x&(x-1) unsets the rightmost set bit
//x&(-x) isloates the rightmost set bit
//x-(x&-(-x)) removing the last set bit one by one
//x-1 unsets the rightmost set bit and sets all the trailing zeros
// x=100100110000;
// x-1==100100101111
// x|(x-1) all the trailing zeros are set
// sum(a,b)=(a&b)+(a|b);
// sum(a,b)=(a^b)+2*(a&b);
// a^b is addition without the carry and a&b is the carry hence multiply by 2 to shift
// product of factors = n^(x/2) where x=number of factors
//ax+by=g
//ax+by=c
// let Xg and Yg be value got from ax+by=g using ext_gcd
// solution of ax+by=c [X0,Y0]=[Xg*c/g,Yg*c/g]
// a(x+b/g)+b(y-a/g)=c;
// X1=X0+k*(b/g) Y1=Y0-k*(a/g)
int gcd_ext(int a,int b,int&x,int&y){
//base case
if(b==0){
x=1,y=0;
return a;
}
int x1,y1;
int g=gcd_ext(b,a%b,x1,y1);
x=y1;
y=x1-(a/b)*y1;
return g;
}
//chinese reminder theroem
// x==(a1%m1)
// x==(a2%m2)
// ...
//m1,m2,m3... are pairwise coprime
// let m=m1*m2*m3...
// then there exist exactly one x in [0,m-1] that satisfies the congrunecy
// x= a1*(m/m1)*inv(m/m1)%m1+a2*(m/m2)*inv(m/m2)%m2....
#define f first
#define s second
using ll=long long;
using ld=long double;
const long long inf=1e18+1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
long long M=998244353;
///M=k*a+r M is prime
// k=(M/a) r=M%a
// 0=(K*a+r)%M
// inv(a)%M=(M-inv(r)*(m/a))%M
long long exp(long long x,long long y){
long long res=1;
while(y){
if(y&1){
res=(res*x)%M;
}
y=y>>1;
x=(x*x)%M;
}
return res;
}
long long dist(int xi,int yi,int xj,int yj){
return (xi-xj)*1ll*(xi-xj)+(yi-yj)*1ll*(yi-yj);
}
class dsu{
public:
vector<int>par;
vector<int>size;
public:
dsu(int n){
par.resize(n);
size.resize(n);
for(int i=0;i<n;i++){
par[i]=i;
size[i]=1;
}
}
int find(int u){
if(u==par[u]){return u;}
return par[u]=find(par[u]);
}
void unite(int u,int v){
int par_u=find(u);
int par_v=find(v);
if(par_u==par_v){return;}
// assumig par_u is smaller
if(size[par_u]>size[par_v]){
swap(par_u,par_v);
}
size[par_v]+=size[par_u];
par[par_u]=par_v;
return;
}
bool connected(int u,int v){
return (find(u)==find(v));
}
};
class fenwick{
public:
vector<long long>bit;
int n;
fenwick(int n,vector<int>&a){
this->n=n;
bit.assign(n+1,0LL);
for(int i=0;i<n;i++){
bit[i+1]=a[i];
}
for(int i=1;i<=n;i++){
int r=i+(i&(-i));
if(r<=n)bit[r]+=bit[i];
}
}
void update(int r,int val){
int cur_r=r+1;
while(cur_r<=n){
bit[cur_r]+=val;
cur_r=cur_r+(cur_r&(-cur_r));
}
return ;
}
long long sum(int r){
int cur_r=r+1;
long long ret_sum=0;
while(cur_r>0){
ret_sum+=bit[cur_r];
cur_r=cur_r-(cur_r&(-cur_r));
}
return ret_sum;
}
long long sum_qry(int l,int r){
return sum(r)-sum(l-1);
}
};
class sgt{
public:
vector<long long>t;
sgt(int n){
t.assign(4*n, 0);
}
void build(int tl,int tr,int v,vector<long long>&a){
if(tl==tr){
t[v]=a[tl];
return;
}
int mid=(tl+tr)/2;
build(tl,mid,v*2+1,a);
build(mid+1,tr,v*2+2,a);
t[v] =t[v*2+1]+t[v*2+2];
}
void update(int v,long long val,int pos,int tl,int tr){
if(tl==tr){
t[v]=val;
return;
}
int mid = (tl + tr)/2;
if(pos<=mid) update(v*2+1,val,pos,tl,mid);
else update(v*2+2,val,pos,mid+1,tr);
t[v]=t[v*2+1]+t[v*2+2];
}
long long query(int l,int r,int tl,int tr,int v){
if(l>r) return 0;
if(l==tl&&r==tr)return t[v];
int mid=(tl+tr)/2;
return query(l,min(r,mid),tl,mid,v*2+1)
+ query(max(l,mid+1),r,mid+1,tr,v*2+2);
}
};
using ll =long long;
using pll=pair<long long,long long>;
using pii=pair<int,int>;
#define all(x) (x).begin(),(x).end()
#define all_rev(x) (x).rbegin(),(x).rend()
typedef vector<int> vi;
typedef vector<long long>vll;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
vector<vector<int>>g;
vector<vector<pii>>gwt;
vector<bool>vis;
vector<int>v;
std::vector<ll> pf;
const int mx=1e6+1;
// phi[i]=i*multiply(1-1/prime_factors)
//phi(i*j)=phi(i)*phi(j)*g/phi(g)
//(a^(n))%m==== (a^(n%phi(m)))%m
vector<int>phi(mx+1);
void cal_phi(){
for(int i=0;i<=mx;i++){
phi[i]=i;
}
for(int i=2;i<=mx;i++){
if(phi[i]==i){
for(int j=i;j<=mx;j=j+i){
phi[j]=(phi[j])-(phi[j]/i);
}
}
}
}
vector<bool>prime(mx,true),lpf(mx);
void seiv_algo(){
prime[0]=prime[1]=false;
for(int i=2;i<mx;i++){
if(prime[i]){
lpf[i]=i;
for(int j=2*i;j<mx;j=j+i){
prime[j]=false;
if(lpf[j]==0)lpf[j]=i;
}
}
}
}
ll mod_inv(ll x){
return( M+exp(x,M-2))%M;
}
// number of dearrangement== n!(sum(-1^k/k!)) i.e n!(1/0!-1/1!+1/2!-1/3!...)
// let 1st person get ith hat
// then case1: i also get the 1st hat .... i can have n-1 values
// then now there are n-2 hats to solve
// giving as (n-1)*(f(n-2))
// case2: i doesn't get the 1st hat and i can take n-1 values, so now we need to get f(n-1) values
// giving us n-1*f(n-1);
// hence f(n)=(n-1)*(f(n-1)+f(n-2)); dearrangements
//STARS AND BAR (k stars and n bars) ((k+n-1)C(n-1)) x1+x2+x3...xn=k Xi>=0; or N boxes and K balls, can put multiple balls in a box
// x1+p+x2+p+x3+p....=k
//x1+x2+...=k-p-p-p...
//x1+x2+x3..=k'
// k'+(n-1)C(n-1)
//pos[0]=true;
//for(k=0;k<n;k++){for(x=W;x>=0;x--;){if(pos[x]){pos[x+wt[k]]=true;}}}
void solve() {
int W,n;cin>>W>>n;
int tot=0;
vector<array<int,3>>v(n);
vector<int>wt,val;
for(int i=0;i<n;i++){
cin>>v[i][0]>>v[i][1]>>v[i][2];
tot+=v[i][2];
for(int j=0;j<v[i][2];j++){
wt.push_back(v[i][1]);
val.push_back(v[i][0]);
}
}
//cout<<v[0][1];
vector<int>dp(W+1,0);
dp[0]=0;
for(int i=0;i<tot;i++){
for(int j=W;j>=0;j--){
if(j-wt[i]>=0&&dp[j-wt[i]]+val[i]>dp[j]){
dp[j]=dp[j-wt[i]]+val[i];
}
}
}
cout<<dp[W];
}
int main(){
//freopen("team.in","r",stdin);
//freopen("team.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
}
// 4
// 2
// 1
// 2
// 3
// 4
