#include <bits/stdc++.h>
#define el '\n'
using namespace std;
struct Goods {
int w;
long long val;
Goods(int W,long long V): w(W), val(V) {}
};
int S, N;
vector<Goods> goods;
void init() {
cin >> S >> N;
for (int i=0;i<N;i++) {
long long v;
int w, k;
cin >> v >> w >> k;
int pow2 = 1;
while (k > 0) {
int take = min(pow2, k);
int newW = w * take;
long long newVal = v * 1ll * take;
if (newW <= S) {
goods.emplace_back(newW, newVal);
}
k -= take;
pow2 <<= 1;
}
}
}
void sol() {
vector<long long> dp(S+1, 0);
for (Goods x : goods) {
int w = x.w;
long long val = x.val;
for (int j=S; j>=w; j--) {
dp[j] = max(dp[j], dp[j-w] + val);
}
}
cout << *max_element(dp.begin(), dp.end()) << el;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
sol();
}
