#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
ll V[mn], W[mn], K[mn], dp[2][2020];
struct dqTrick {
deque<ll> dq;
void push (ll x) {
while (dq.size() && dq.back() < x) dq.pop_back();
dq.push_back(x);
}
void pop (ll x) {
if (dq.size() && dq.front() == x) dq.pop_front();
}
ll best() { return (dq.empty() ? LLONG_MIN : dq.front()); }
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int S, n; cin >> S >> n;
for (int i = 1; i <= n; i++) cin >> V[i] >> W[i] >> K[i];
for (int i = 1; i <= n; i++) {
int t = i & 1;
vector<dqTrick> opt(W[i]);
for (int j = 0; j <= S; j++) {
int R = j % W[i], D = j / W[i];
opt[R].push(dp[t ^ 1][j] - D * V[i]);
if (j >= W[i] * (K[i] + 1))
opt[R].pop(dp[t ^ 1][j - W[i] * (K[i] + 1)] - (D - K[i] - 1) * V[i]);
dp[t][j] = opt[R].best() + D * V[i];
}
}
cout << dp[n & 1][S];
return 0;
}
