#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn = 2005;
int n, S;
vector<int> weight, val;
ll dp[maxn];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> S >> n;
for (int i = 1; i <= n; i++) {
int v, w, k;
cin >> v >> w >> k;
k = min(k, S / w);
int cnt = 1;
while (k > 0) {
int take = min(cnt, k);
k -= take;
weight.push_back(w * take);
val.push_back(v * take);
cnt <<= 1;
}
}
for (int i = 0; i < (int)weight.size(); i++) {
for (int s = S; s >= weight[i]; s--) {
dp[s] = max(dp[s], dp[s - weight[i]] + val[i]);
}
}
cout << dp[S];
}
