// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int maxWeight, numItems;
cin >> maxWeight >> numItems;
vector<array<int, 2>> items;
for(int i = 0; i < numItems; i++) {
int value, weight, copies;
cin >> value >> weight >> copies;
copies = min(copies, maxWeight);
int part = 1;
while(copies >= part) {
items.push_back({value * part, weight * part});
copies -= part;
part *= 2;
}
if(copies > 0) {
items.push_back({value * part, weight * part});
}
}
numItems = items.size();
vector<int> dp(maxWeight + 1);
for(int i = 0; i < numItems; i++) {
for(int j = maxWeight; j - items[i][1] >= 0; j--) {
dp[j] = max(dp[j], dp[j - items[i][1]] + items[i][0]);
}
}
cout << dp[maxWeight];
}
