#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, s;
cin >> s >> n;
matrix pos(s + 1, vi(0));
rep(i, 0, n){
ll V, W, K;
cin >> V >> W >> K;
ll c = 1;
while(K > c){
if(W * c <= s){
pos[W * c].push_back(V * c);
}
K -= c;
c <<= 1;
}
if(W * K <= s){
pos[W * K].push_back(V * K);
}
}
rep(i, 0, s + 1){
sort(pos[i].begin(), pos[i].end(), greater<ll>());
}
matrix next(s + 1, vi(s + 1, 0));
vi dp(s + 1, 0);
rep(i, 0, s + 1){
ll ind = -1;
ll best = 0;
rep(j, 0, i){
if(pos[i - j].size() == next[j][i - j]) continue;
ll curr = pos[i - j][next[j][i - j]];
if(curr + dp[j] > best){
ind = j;
best = curr + dp[j];
}
}
if(ind != -1){
dp[i] = best;
next[i] = next[ind];
next[i][i - ind]++;
}
}
ll m = 0;
rep(i, 0, s + 1) m = max(dp[i], m);
cout << m << endl;
}
