#include <bits/stdc++.h>
using namespace std;
inline void fastInput(int &num) {
num = 0;
char ch = getchar();
bool neg = false;
if(ch == '-') {
ch = getchar();
while(ch >= '0' && ch <= '9') {
num = (num << 3) + (num << 1) + (ch - '0');
ch = getchar();
}
if(neg) num = -num;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n;
fastInput(s);
fastInput(n);
vector<pair<int, int>> items; // {value, weight}
for (int i = 0; i < n; ++i) {
int v, w, k;
fastInput(v);
fastInput(w);
fastInput(k);
int count = 1;
while (k > 0) {
int currentCount = min(count, k);
items.push_back({currentCount * v, currentCount * w});
k -= currentCount;
count <<= 1;
}
}
vector<int> dp(s + 1, 0);
for (const auto &item : items) {
int v = item.first, w = item.second;
for (int j = s; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[s] << '\n';
return 0;
}
