#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> solve(ll x, vector<ll> &res){
res.clear();
for (ll p = 1; p <= x; p <<= 1){
res.push_back(p);
x -= p;
}
if (x > 0) res.push_back(x);
return res;
}
int main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<ll> dp(s+1, 0);
for (int i = 0; i<n; i++){
ll a, b, c;
cin >> a >> b >> c;
if (b>s){continue;}
vector<ll> res;
solve(c, res);
for (ll x : res){
ll n1 = b*x;
ll a1 = a*x;
for (ll j = s; j>n1; j--){
if (dp[j-n1]!=0) dp[j]=max(dp[j-n1] + a1, dp[j]);
}
if (n1<s+1) dp[n1] = max(dp[n1], a1);
}
}
// for (auto i : dp){
// cout << i << " ";
// }
// cout << "\n";
ll m = 0;
for (auto i : dp){
m = max(m, i);
}
cout << m;
return 0;
}
