#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <pstl/utils.h>
// using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define pi pair<int, int>
#define ull unsigned long long
#define NO {cout << "NO\n"; return;}
#define YES {cout << "YES\n"; return;}
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define cin_vector(v) for(auto &it:v) cin >> it;
#define cout_vector(v) for(auto &it:v) cout << it << ' ';
#define NEXT_POWER_OF_TWO(x) \
( ((x) <= 1) ? 1 : 1ll << (64 - __builtin_clzll((x) - 1)) )
// template<typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1e6+1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
vector<vector<ll>> divs(N);
vb Prime(N);
vl primes;
vi phi(N);
vl facts(N);
// void Erase(ordered_set<long long> &s, long long val) {
// int order = s.order_of_key(val);
// auto it = s.find_by_order(order);
// if (it != s.end() && *it == val) s.erase(it);
// }
vl getDivisors(ll n) {
vl divisors;
for (ll i = 1; i * i <= n; i++) {
// i <= sqrt(n) -> i*i <= n
if (n % i == 0) {
divisors.push_back(i);
if (n / i != i) divisors.push_back(n / i);
}
}
// sort(all(divisors));
return divisors;
}
vl sieve(ll n) {
vl primes;
vb isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// n * (1/2 + 1/3 + 1/5+ 1/7 + 1/9 + ...)
// n * summation (1/p) where p is prime number
// n * log(log(n))
for (int j = i * i; j <= n; j += i) // Harmonic Series -> log(n)
isPrime[j] = false;
}
}
for (int p = 2; p <= n; p++) {
if (isPrime[p]) primes.push_back(p);
}
return primes;
}
int Phi(int n) {
int ans = n;
for (int p = 2; p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) { n /= p; }
ans -= ans / p;
}
}
if (n > 1) { ans -= ans / n; }
return ans;
}
void precomputePhi() {
for (ll i = 1; i < N; i++) { phi[i] = i; }
for (ll i = 2; i < N; i++) {
// If i is prime
if (phi[i] == i) {
for (int j = i; j < N; j += i) { phi[j] -= phi[j] / i; }
}
}
}
int countTwos(int n) {
int count = 0;
while (n % 2 == 0) {
n /= 2;
count++;
}
return count;
}
// O(n*log(n))
void preComputeDivisors() {
for (ll i = 1; i < N; i++) {
for (ll j = i; j < N; j += i) {
divs[j].push_back(i);
}
}
}
map<ll, ll> primeFactorization(ll n) {
map<ll, ll> factors;
for (ll i = 2; i * i <= n; i++) {
ll count = 0;
while (n % i == 0) {
count++;
n /= i;
}
if (count > 0)
factors[i] += count;
}
if (n > 1) factors[n] = 1;
return factors;
}
// counts the power of a prime(p) in the prime factorization of (n)
ll legendreFormula(ll n, ll p) {
ll cnt = 0;
while (n > 0) {
n /= p;
cnt += n;
}
return cnt;
}
bool isPowerOf2(int n) {
if (n == 0) return false;
return !(n & (n - 1));
// Another way (counting ones)
// return __builtin_popcount(n) == 1;
}
int toggleBit(int n, int bit) {
return n ^ (1 << bit);
}
int XorFrom0ToN(int n) {
if (n % 4 == 0) return n;
if (n % 4 == 1) return 1;
if (n % 4 == 2) return n + 1;
return 0;
}
int findHighest(ll x) {
for (int i = 63; i >= 0; i--) {
if ((x >> i) & 1LL) return i;
}
return -1;
}
int ask(int st, int en) {
int andd;
cout << "and " << st << ' ' << en << endl;
cout.flush();
cin >> andd;
int orr;
cout << "or " << st << ' ' << en << endl;
cout.flush();
cin >> orr;
int ret = andd+orr;
return ret;
}
ll exp(ll x, ll n, ll m) {
assert(n >= 0);
x %= m;
ll res = 1;
while (n > 0) {
if (n & 1) {res = res * x % m;}
x = x*x % m;
n >>= 1;
}
return res;
}
ll inv(ll x) { return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD; }
ll fact(ll n){
ll res = 1;
for(int i = 1; i <= n; i++)
res = (res * i) % MOD;
return res;
}
// bool check(ll n) {
// bool prime = true;
// for (ll i = 2; i*i <= n; i++) {
// if (n % i == 0) {
// prime = false;
// break;
// }
// }
// return prime;
// }
void solve() {
ll s, n; cin >> s >> n;
vl val(n), wei(n), amo(n);
for (int i = 0; i < n; i++) {
cin >> val[i] >> wei[i] >> amo[i];
}
vector<pair<ll,ll>> virtual_items;
for (ll i = 0; i < n; i++) {
ll k = min(amo[i], s / wei[i]);
ll p = 1;
while (k > 0) {
ll take = min(p, k);
virtual_items.push_back({take*wei[i], take*val[i]});
k -= take;
p *= 2;
}
}
vl dp(s+1, 0);
for (auto v : virtual_items) {
for (ll w = s; w >= v.first; w--) {
dp[w] = max(dp[w], dp[w - v.first] + v.second) ;
}
}
cout << *max_element(dp.begin(), dp.end());
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("sumdiv.in", "r", stdin);
// freopen("sumdiv.out", "w", stdout);
// Prime = sieve(N);
// primes = sieve(N);
// preComputeDivisors();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
