#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int dp[N];
void solve() {
int S, itemsCount;
cin >> S >> itemsCount;
// 1. Clear DP for multiple test cases
memset(dp, 0, sizeof(dp));
// 2. Change 'a' to a vector to prevent items of the same weight from overwriting each other
// Stores pairs of {weight, value}
vector<pair<int, int>> a;
for(int i = 0; i < itemsCount; ++i){
int v, w, k; cin >> v >> w >> k;
for(int j = 1; j <= k; j*=2){
if(j * w <= S) a.push_back({j * w, j * v}); // Safely append
k -= j;
}
if(k > 0 && k * w <= S) a.push_back({k * w, k * v}); // Safely append
}
// 3. Iterate through all safely stored items
for(auto item : a){
int weight = item.first;
int value = item.second;
// Your perfectly corrected backwards loop
for(int j = S - weight; j >= 0; --j) {
dp[j + weight] = max(dp[j + weight], dp[j] + value);
}
}
cout << *max_element(dp, dp + S + 1) << "\n";
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
