#include <iostream>
#include <limits.h>
#include <vector>
#include <array>
using namespace std;
typedef long long ll;
// int solvedp(int goal, vector<array<int, 2>>& items, vector<vector<int>>& memo, int idx) {
// if (goal < 0) return INT_MIN;
// if (goal == 0 || idx >= items.size()) return 0;
// if (memo[goal][idx] != -1) return memo[goal][idx];
// int skip = solvedp(goal, items, memo, idx+1);
// int take = solvedp(goal - items[idx][W], items, memo, idx+1);
// if (take >= 0) {
// take += items[idx][V];
// }
// int best = max(skip, take);
// memo[goal][idx] = best;
// return best;
// }
void solve() {
int n;
ll s;
cin >> s >> n;
vector<ll> dp(s+1, 0);
for (int i = 0; i < n; ++i) {
ll v, w, q;
cin >> v >> w >> q;
// fucking binary optimization
for (ll k = 1; q > 0; k <<= 1) {
ll take = min(k, q);
ll chunkV = take * v;
ll chunkW = take * w;
if (chunkW <= s) {
for (ll j = s; j >= chunkW; --j) {
dp[j] = max(dp[j], dp[j - chunkW] + chunkV);
}
}
q -= take;
}
}
cout << dp[s] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
