#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
/*ll dp(int i, int l, int x, int y, vector<ll>& memo, vector<ll>& v){
if(i>=x or l>=v[x]) return 0;
if(memo[i] != -1) return memo[i];
ll n_c = 1000000;
if(v[i] <= l) n_c = dp(i+1,l,x,y,memo,v);
return memo[i] = min(dp(i+1, v[i]+y, x, y, memo,v)+1, n_c);
}
int main(){
int x,y; cin >> x >> y;
vector<ll> v(x);
for(int i=0; i<x; i++) cin >> v[i];
vector<ll> memo(x, -1);
cout << dp(0,0,x,y,memo,v)<<endl;
return 0;
}
*/
struct item{
ll v,w;
};
const int maxn = 1e6;
item listt[maxn];
int main(){ _
ll n, W;
cin >> W >> n;
const ll MOD = 1000000007;
int index = 0;
for(int i=1; i<=n; i++){
ll p,h,k;
cin >> h >> p >> k;
ll c = 1;
while(k>c){
k-=c;
listt[++index].w = c*p;
listt[index].v = c*h;
c*=2;
}
listt[++index].w = k*p;
listt[index].v = k*h;
}
vector<ll> dp(W+1, 0);
for(int i=1; i<=index; i++){
for(int j=W; j>=listt[i].w; j--){
dp[j] = max(dp[j], dp[j-listt[i].w] + listt[i].v);
}
}
cout << dp[W] << endl;
}
