// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(ll i = a; i <= b; ++i)
#define FOR_NEG(i, a, b) for(ll i = a; i >= b; --i)
#define FOR_EACH(a, b) for(auto a : b)
ll solve(ll x, ll n, vector<ll>& weights, vector<ll>& values) {
vector<vector<ll>> dp(n+1 , vector<ll>(x+1, 0));
for (ll i = 0; i <= n; ++i) { dp[i][0] = 0; }
for (ll i = 1; i <= n; ++i) {
for (ll j = 1; j <= x; ++j) { // Allow duplicates
ll if_notUse_ans = 0 + dp[i-1][j];
ll if_use_ans = 0;
if (j - weights[i-1] >= 0) { if_use_ans = values[i-1] + dp[i-1][j - weights[i-1]]; }
dp[i][j] = max(if_use_ans, if_notUse_ans);
}
}
return dp[n][x];
}
ll solve_optimal(ll x, ll n, vector<ll>& weights, vector<ll>& values){
vector<ll> dp(x+1, 0);
FOR(i, 1, n) {
FOR_NEG(j, x, 1) {
ll if_notUse_ans = 0 + dp[j];
ll if_use_ans = 0;
if(j - weights[i-1] >= 0) { if_use_ans = values[i-1] + dp[j - weights[i-1]]; }
dp[j] = max(if_use_ans, if_notUse_ans);
}
}
return dp[x];
}
int main() {
// Inputs
ll s, n;
cin >> s >> n;
vector<ll> weights;
vector<ll> values;
FOR(i, 0, n-1) {
ll v, w, k;
cin >> v >> w >> k;
FOR(j, 1, k) {
values.push_back(v);
weights.push_back(w);
}
}
//
ll answer;
// answer = solve(s, weights.size(), weights, values);
answer = solve_optimal(s, weights.size(), weights, values);
cout << answer;
return 0;
}
