#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, s;
cin >> s >> n;
vector<ll> v(n), w(n), k(n);
for (int i = 0; i < n; ++i){
cin >> v[i] >> w[i] >> k[i];
}
vector<ll> dp(s + 1, -1);
dp[0] = 0;
for (int i = 0; i < n; ++i){
vector<ll> index(w[i], 3000);
vector<deque<ll>> best(w[i]);
for (int j = s; j >= 0; --j){
int ind = j % w[i];
if (index[ind] == 3000) index[ind] = j;
while (index[ind] >= 0 && (j - index[ind])/w[i] <= k[i]){
int z = index[ind];
ll val = dp[z] + ((s - z)/w[i])*v[i];
index[ind] -= w[i];
while (dp[z] >= 0 && !best[ind].empty() && best[ind].back() < val){
best[ind].pop_back();
}
if (dp[z] >= 0) best[ind].push_back(val);
}
ll mult = ((s - j)/w[i])*v[i];
ll u = dp[j] + mult;
if (!best[ind].empty() && best[ind].front() == u) best[ind].pop_front();
if (!best[ind].empty()){
ll v = best[ind].front() - mult;
dp[j] = max(dp[j], v);
}
}
}
ll ans = 0;
for (int i = 0; i <= s; ++i) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
