#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> f[3005];
int n, dp[3005];
void add(int v, int w, int k)
{
if(k == 0) return;
int num = (k+1)/2;
if(w*num <= n) f[w*num].push_back(v*num);
add(v, w, k/2);
}
void add_object(int w, int v)
{
for(int i = n; i >= w; i--) dp[i] = max(dp[i], dp[i-w] + v);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m; cin>>n>>m;
for(int i = 1; i <= m; i++){
int v, w, k; cin>>v>>w>>k;
add(v, w, k);
}
for(int i = 1; i <= n; i++){
sort(f[i].begin(), f[i].end(), greater<int>());
while(f[i].size() > n/i) f[i].pop_back();
}
for(int i = 1; i <= n; i++){
for(int j : f[i]) add_object(i, j);
}
int ans = 0;
for(int i = 0; i <= n; i++) ans = max(ans, dp[i]);
cout<<ans;
}
