#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define debug cout << "Debug\n"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
inline void USACO(string filename){
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
ll mod = 998244353;
ll dp[2001];
void solve() {
ll s, n; cin >> s >> n;
for (int i = 0; i < n; i++) {
ll v, w, k; cin >> v >> w >> k;
k = min(k, s / w + (s % w != 0));
for (ll p = 1; k > 0; p <<= 1) {
ll num = min(k, p);
ll curr_v = v * num, curr_w = w * num;
for (ll x = s; x >= curr_w; x--) dp[x] = max(dp[x], dp[x - curr_w] + curr_v);
k -= num;
}
}
cout << dp[s] << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
