#include <bits/stdc++.h>
#define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
#define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
#define debug(x) cout << "[DEBUG]: " << #x << " = " << x << endl;
#define log2(x) ((x) > -1 ? __lg((x)) : 0)
#define BITS(x) (1 << (x))
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 30;
const int INF = 1e18;
int S, n;
struct Info {
int v, w, k;
} A[N];
namespace sub3 {
bool check() {
FOR(i, 1, n, 1) {
if (A[i].k > 10) return false;
}
return (n <= 100);
}
int dp[105][2005];
void solve() {
FOR(i, 1, n, 1) {
int times = A[i].k;
int weight = A[i].w;
FOR(K, weight, S, 1) {
dp[i][K] = dp[i - 1][K];
FOR(t, 1, min(times, K / weight), 1) {
if (K - weight * t >= 0) {
dp[i][K] = max(dp[i][K], dp[i - 1][K - weight * t] + A[i].v * t);
}
}
}
}
cout << dp[n][S] << endl;
}
}
namespace sub4 {
int dp[3150][2005];
bool check() {
FOR(i, 1, n, 1) {
if (A[i].k > 1e9) return false;
}
return (n <= 100);
}
void solve() {
vector <Info> Arr; Arr.reserve(n + 5);
Arr.push_back({-1, -1, -1});
FOR(i, 1, n, 1) {
int values = A[i].v;
int weight = A[i].w;
int times = A[i].k;
FOR(bit, 0, LG, 1) {
int T = BITS(bit);
if (times >= T) {
times -= T;
Arr.push_back({values * T, weight * T, 1});
}
else if (times > 0){
Arr.push_back({values * times, weight * times, 1});
break;
}
}
}
//
int len = Arr.size() - 1;
FOR(i, 1, len, 1) {
int times = Arr[i].k;
int weight = Arr[i].w;
FOR(K, weight, S, 1) {
dp[i][K] = dp[i - 1][K];
if (K - weight >= 0) {
dp[i][K] = max(dp[i][K], dp[i - 1][K - weight] + Arr[i].v);
}
}
}
cout << dp[len][S] << endl;
}
}
void solve() {
cin >> S >> n;
FOR(i, 1, n, 1) {
int v, w, k; cin >> v >> w >> k;
A[i] = {v, w, k};
}
if (sub3::check()) {
sub3::solve();
}
else if (sub4::check()) {
sub4::solve();
}
}
signed main() {
#define name "task"
if (ifstream(name".inp")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
