#include <bits/stdc++.h>
using namespace std;
#define int long long
#define a first
#define b second
#define pb push_back
#define endl '\n'
signed main() {
//your code goes here
ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
int s, n; cin >> s >> n;
vector <vector <int>> item = {};
for(int i = 0; i < n; i++) {
int v, w, k; cin >> v >> w >> k;
item.pb({v, w, k});
}
int dp[n+2][s+2];
memset(dp, 0, sizeof(dp));
// cout << item.size() << " " << n << endl;
for(int i = 0; i < n; i++) {
int v = item[i][0]; int w = item[i][1]; int k = item[i][2];
for(int j = 0; j <= k; j++) {
if(j > s) {break;}
for(int l = 0; l <= s; l++) {
// cout << "HELLO" << " " << v << " " << j << " " << i << " " << l << endl;
if((l+(j*w)) > s) {break;}
dp[i+1][l+(j*w)] = max(dp[i+1][l+(j*w)], dp[i][l]+(j*v));
}
}
}
int maxv = 0;
for(int i = 0; i <= s; i++) maxv = max(maxv, dp[n][i]);
cout << maxv << endl;
return 0;
}
