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