#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int N, S; cin >> S >> N;
vector<long long> vfw(S+1, 0);
vector<long long> aus(S+1);
auto upd = [&](int v, int w) {
for (int i = S; i >= w; i--) {
aus[i] = max(vfw[i], vfw[i-w]+v);
}
for (int i = min(S, w-1); i >= 0; i--) aus[i] = vfw[i];
};
for (int i = 0; i < N; i++) {
long long V, W, K; cin >> V >> W >> K;
for (long long k = 1; k <= K; k<<=1) {
upd(V*k, W*k);
K-=k;
vfw = aus;
}
if (K > 0) upd(V*K, W*K);
vfw = aus;
}
long long best = 0;
for (int i = 0; i <= S; i++) {
best = max(best, vfw[i]);
}
cout << best << "\n";
}
