#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int S = 2005;
int n, s;
int v[N], w[N], a[N];
ll dp[S];
void Solve() {
FOR(i, 1, n) {
ll pw = 1;
while(a[i] >= pw && pw * w[i] <= s) {
FOD(j, s, pw * w[i]) dp[j] = max(dp[j], dp[j - pw * w[i]] + 1LL * v[i] * pw);
a[i] -= pw;
pw <<= 1;
}
if(a[i] > 0 && a[i] * w[i] <= s) FOD(j, s, a[i] * w[i]) dp[j] = max(dp[j], dp[j - a[i] * w[i]] + 1LL * a[i] * v[i]);
}
ll ans = 0;
FOR(i, 0, s) ans = max(ans, dp[i]);
cout << ans << '\n';
}
signed main() {
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) {
cin >> s >> n;
FOR(i, 1, n) cin >> v[i] >> w[i] >> a[i];
Solve();
}
}
