#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define forf(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ford(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define REP(i,v) for(auto i: v)
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x),end(x)
#define MASK(i) (1LL<<i)
#define bit(x,i) ((x<<iLL)&1)
#define file "A"
const int N= 2e5+5;
const int mod= 1e9+7;
const ll oo= (ll) 1e16;
int n,w;
ll dp[N];
vector<pll> items;
void solve() {
cin>>w>>n;
forr(i,1,n) {
int x,y,z;
cin>>y>>x>>z;
int k=1;
while (z>k) {
if (1LL*x*k>(ll) w) break;
items.pb({x*k,y*k});
z-=k;
k*=2;
}
if (z) items.pb({x*z,y*z});
}
memset(dp,-63,sizeof(dp));
dp[0]=0;
for(pii x: items) {
ford(i,w,x.fi) {
dp[i]=max(dp[i],dp[i-x.fi]+x.se);
}
}
ll ans=0;
forr(i,0,w) ans=max(ans,dp[i]);
cout<<ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
int test=1;
// cin>>test;
while (test--) {
solve();
}
return 0;
}
