/*
author : PakinDioxide
created : 26/04/2025 23:45
task : ์์NOI18_knapsack
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dp[2005], ok[2005];
vector <pair <int, int>> V[2005];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int s, n;
cin >> s >> n;
ok[0] = 1;
while (n--) {
int v, w, k;
cin >> v >> w >> k;
for (int i = 0; i <= s; i++) {V[i].clear(); if (ok[i]) V[i].emplace_back(dp[i], 0);}
for (int i = w; i <= s; i++) for (auto &[x, y] : V[i-w]) if (y < k) V[i].emplace_back(x+v, y+1), dp[i] = max(dp[i], x+v), ok[i] = 1;
}
int mx = 0;
for (int i = 0; i <= s; i++) mx = max(mx, dp[i]);
cout << mx << '\n';
}
