#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAX = 1e6+7;
const ll MOD = 1e9+7;
ll n,M;
vector <ll> vec[2001];
void solve() {
cin >> M >> n;
for(ll i=1; i<=n; ++i) {
ll w,v,a;
cin >> v >> w >> a;
a = min(a, M/w);
ll pw = 1;
while(a > 0) {
ll take = min(pw,a);
vec[w*take].pb(v*take);
a -= take;
pw *=2;
}
}
for(ll i=1; i<=M; ++i)
sort(vec[i].begin(), vec[i].end(), greater <ll>());
vector <ll> dp(M+1, 0);
for(ll i=1; i<=M; ++i) {
for(ll j=0; j<min((ll)vec[i].size(), M/i); ++j) {
for(ll k=M; k>=i; k--)
dp[k] = max(dp[k-i] + vec[i][j], dp[k]);
}
}
cout << dp[M];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//if(fopen("TASK.INP","r")) {
// freopen("TASK.INP","r",stdin);
// freopen("TASK.OUT","w",stdout);
//}
solve();
cerr << "\n" << "Time elapsed: " << TIME << "s\n";
return 0;
}
