#include <bits/stdc++.h>
using namespace std;
int helper(vector<vector<long long>>&dp,int i,long long w,int n,vector<long long>&values,vector<long long>&weights){
if(w == 0){
return 0;
}
if( i == n)
return 0;
if(dp[i][w] != -1)
return dp[i][w];
int a = helper(dp,i+1,w,n,values,weights);
int b = w >= weights[i] ? helper(dp,i+1,w - weights[i],n,values,weights) + values[i]: 0;
return dp[i][w] = max(a,b);
}
int main() {
// your code goes here
long long n,s;
cin>>s>>n;
vector<int>w(n),v(n),k(n);
int sum = 0;
vector<long long>values,weights;
for(int i=0;i<n;i++){
cin>>v[i]>>w[i]>>k[i];
long long sum = 0;
for(int j=0;j<32;j++){
if(sum + (1<<j) > k[i]){
values.push_back((long long)v[i]*(long long)(k[i]-sum));
weights.push_back((long long)w[i]*(long long)(k[i]-sum));
break;
}
sum += (1<<j);
values.push_back((long long)v[i]*(long long)(1<<j));
weights.push_back((long long)w[i]*(long long)(1<<j));
}
}
int ans = 0;
int m = values.size();
vector<vector<long long>>dp(m,vector<long long>(s + 1,-1));
cout<<helper(dp,0,s,m,values,weights);
}
