#include <bits/stdc++.h>
using namespace std;
//debug
#define dbg(a) cout << #a << " : " << a << endl;
#define dbga(a, l, r) cout << #a << " : "; for(long long abc = l; abc <= r; ++abc) cout << a[abc] << " "; cout << endl
#define dbgv(a) cout << #a << " : "; for(auto abc: a) cout << abc << " "; cout << endl
//Finite Field
const int MOD = 1e9 + 7;
void add(int &a, int b, int mod = MOD){ a += b; while (a < 0) a += mod; while (a >= mod) a -= mod; }
int sum(int a, int b, int mod = MOD){ return add(a, b, mod), a; }
void mul(int &a, int b, int mod = MOD){ a = (a * 1LL * b) % mod; }
int prod(int a, int b, int mod = MOD){ return mul(a, b, mod), a; }
int bpow(int a, int b, int mod = MOD){ int ans = 1; while (b){ if (b & 1){ mul(ans, a, mod); } mul(a, a, mod); b >>= 1; } return ans; }
int Inv(int a, int mod = MOD){ return bpow(a, mod - 2, mod); }
int Div(int a, int b, int mod = MOD) { return prod(a, Inv(b, mod), mod); }
const int N = 2e5 + 5;
const long long INF = numeric_limits<long long>::max() / 2;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;
int v[N], w[N], k[N];
int dp[2005];
vector <int> a[2005];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, s; cin >> s >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i] >> w[i] >> k[i];
k[i] = min(k[i], s / w[i]);
int pw = 1;
while (pw <= k[i]){
a[w[i] * pw].push_back(v[i] * pw);
k[i] -= pw;
}
if (k[i]){
a[w[i] * k[i]].push_back(v[i] * k[i]);
}
}
for(int i = 1; i <= s; ++i){
sort(a[i].begin(), a[i].end());
while (!a[i].empty() && i * a[i].size() > s){
a[i].pop_back();
}
}
for(int w = 1; w <= s; ++w){
for(int v : a[w]){
for(int i = s; i >= w; --i){
dp[i] = max(dp[i], dp[i - w] + v);
}
}
}
cout << dp[s];
return 0;
}
