#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 1;
const int S = 1e3 + 1;
#define nl "\n"
#define sp " "
int s, n, w[N], v[N], k[N];
bool s3 = true;
void subtask1(){
ll ans = 0, cur = 0;
for(int i = 1; i<=k[0]; i++){
cur += w[0];
if(cur > s) break;
ans += v[0];
} cout << ans;
return;
}
void subtask3(){
ll m = n*10 + 1, dp[m][s+1]; memset(dp, 0, sizeof dp);
vector<ll> w2, v2;
w2.push_back(0), v2.push_back(0);
for(int i = 1; i<=n; i++) for(int j = 0; j<k[i]; j++){
w2.push_back(w[i]);
v2.push_back(v[i]);
}
for(int i = 0; i<=s; i++){
for(int j = 1; j<w2.size(); j++){
dp[j][i] = dp[j-1][i];
if(w2[j] <= i) dp[j][i] = max(dp[j][i], dp[j-1][i-w2[j]] + v2[j]);
}
} cout << dp[w2.size()-1][s];
return;
}
void subtask4(){
ll dp[n+1][s+1];
for(int i = 0; i<=s; i++){
for(int j = 1; j<=n; j++){
dp[j][i] = dp[j-1][i];
for(int g = 0; g<=k[j]; g++){
if(w[j]*g > i) break;
dp[j][i] = max(dp[j][i], dp[j-1][i-w[j]*g] + v[j]*g);
}
}
} cout << dp[n][s];
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s >> n;
for(int i = 1; i<=n; i++){
cin >> v[i] >> w[i] >> k[i];
if(k[i] > 10) s3 = 0;
}
if(n == 1) subtask1();
else if(n <= 100 && s3) subtask3();
else subtask4();
return 0;
}
