#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
ifstream fin("snakes.in");
ofstream fout("snakes.out");
#include<fstream>
#define pb push_back
#define dq deque
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
struct th{
ll v, w, k;
};
bool cmp(th a, th b){
if(a.w != b.w){
return(a.w < b.w);
}else{
return(a.v > b.v);
}
}
int main()
{
// normal dp knapsack
// but for each object of the same weight, sort them in decreasing value and record how much each reached. Greedy
// Time complexity: o(n * s + slogs)
int s, n; cin >> s >> n;
vt<th>v;
for(int i = 0; i < n; i++){
ll vv, w, k; cin >> vv >> w >> k;
v.pb({vv, w, k});
}
ll dp[n + 1][s + 1];
memset(dp, 0, sizeof(dp));
for(int i = 0; i <= n; i++){
for(int j = 0; j <= s; j++){
if(j == 0 || i == 0)dp[i][j] = 0;
else if(j < v[i - 1].w)dp[i][j] = dp[i - 1][j];
else{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
ll cr = min(j / v[i - 1].w, v[i - 1].k);
//cout << cr << " ";
for(int l = 1; l <= cr; l++){
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1].w * l] + v[i - 1].v * l);
}
}
//cout << dp[i][j] << " ";
}
// cout << "\n";
}
cout << dp[n][s];
return 0;
}
