#include <bits/stdc++.h>
#define int long long
using namespace std;
#define boost ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 1e6 + 12, INF = 1e9 + 7;
signed main () {
boost
int s, n;
cin >> s >> n;
if(n == 1){
int v, w, k;
cin >> v >> w >> k;
int sum = 0;
while(k >= 1 and s >= 0){
if(s - w >= 0 and k - 1 >= 0){
s -= w;
k -= 1;
sum += v;
} else {
break;
}
}
cout << sum;
return 0;
}
vector<int>w(n + 1), v(n + 1), k(n + 1);
for(int i = 1; i <= n; ++i){
cin >> v[i] >> w[i] >> k[i];
}
int dp[112][s + 12];
dp[0][0] = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= s; ++j){
if(w[i] <= j){
for(int just = 1; just <= k[i]; ++just){
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i] * just] + v[i] * just);
}
}
}
}
int mx = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= s; ++j){
mx = max(mx, dp[i][j]);
}
}
cout << mx;
}
