#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pii pair<int,int>
const int NN = 1e5+5;
vector<int> a[3000];
int dp[30005][2005];
int v[NN] , w[NN] , k[NN] ;
struct ha{
int v , w ;
};
vector<ha> lis;
bool ss(int a , int b){
return v[a] > v[b];
}
int di(int vt , int cl){
if(vt<0) return 0;
if(dp[vt][cl]!= -1) return dp[vt][cl];
dp[vt][cl] = di(vt-1 , cl);
if(cl >= lis[vt].w){
dp[vt][cl] = max(dp[vt][cl] ,di(vt-1 , cl-lis[vt].w)+lis[vt].v);
}
return dp[vt][cl];
}
signed main(){
// freopen("connect.in", "r", stdin);
// freopen("connect.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n , s;
cin >> s >> n;
for(int i =1 ;i <= n ;i++){
cin >> v[i] >> w[i] >> k[i] ;
a[w[i]].push_back(i);
}
for(int i = 1 ;i <= s ; i++){
sort(a[i].begin(),a[i].end() , ss);
int sl = 0 ;
int tg = s/i;
for(int l : a[i]){
sl += k[l];
int x = k[l];
for(int j = 0 ; j <= 30 ; j ++){
int op = 1<<j;
if(x>= op){
x-=op;
lis.push_back({v[l]*op ,w[l]*op});
}
}
if(x != 0){
lis.push_back({v[l]*x ,w[l]*x});
}
if(sl > tg) break;
}
}
// for(ha v : lis) cout << v.v <<" "<< v.w<<'\n;
memset(dp , -1 , sizeof(dp));
n = lis.size()-1;
cout << di(n , s);
}
