#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
#define all(x) x.begin(), x.end()
#define ckmin(a,b) a = min(a,b)
#define ckmax(a,b) a = max(a,b)
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
int N, S;
cin >> S >> N;
vll V(N);
vi W(N);
vll K(N);
for (int i=0;i<N;i++) cin >> V[i] >> W[i] >> K[i];
vll dp(S+1, 0);
for (int i=0;i<N;i++) {
vll ndp(S+1, 0);
for (int j=0;j<=W[i] && j<=S;j++) {
priority_queue<pair<ll, int>> maxes;
for (int jp=0;j+jp*W[i]<=S;jp++) {
maxes.push({dp[j + jp*W[i]] - jp*V[i], jp});
// if (jp > K[i]) {
// int njp = jp - (int)(K[i] + 1);
// ll oldmax = dp[j + njp*W[i]] - njp*V[i];
// maxes.erase(maxes.find(oldmax));
// }
while(maxes.top().second < jp - K[i]) maxes.pop();
ll curmax = maxes.top().first;
ckmax(ndp[j+jp*W[i]], curmax + jp*V[i]);
}
// for (int k=0;j-k*W[i]>=0 && k <= K[i];k++) {
// ckmax(ndp[j], dp[j-k*W[i]] + k * V[i]);
// }
}
swap(ndp, dp);
}
cout << dp[S] << endl;
return 0;
}
