// #include "./stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<vector<ll>> vvl;
typedef set<ll> sl;
typedef vector<string> vs;
typedef set<string> ss;
typedef multiset<string> mss;
typedef map<ll, ll> mll;
typedef unordered_set<ll> usl;
typedef deque<ll> dql;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sl;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define SQ(a) (a) * (a)
#define vb vector<bool>
#define pll pair<ll, ll>
#define fast \
ios::sync_with_stdio(false); \
cin.tie(nullptr);
#define print_vec(vec) \
for (auto it : vec) \
{ \
cout << it << " "; \
}
#define print(string) cout << string << endl;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9+7;
ll ncr(ll n, ll r)
{
if (r == 0 || r == n)
return 1;
if (r == 1)
return n;
ll prev = ncr(n - 1, r - 1);
return (n * prev) / r;
}
vector<ll> sieveOfEratosthenes(ll upper_limit)
{
vector<ll> is_prime(upper_limit + 1, 1);
is_prime[0] = is_prime[1] = 0;
for (ll i = 2; i * i <= upper_limit; i++)
{
if (is_prime[i])
{
for (ll j = i * i; j <= upper_limit; j += i)
{
is_prime[j] = 0;
}
}
}
return is_prime;
}
int power(int a, int b) {
int res = 1;
while(b) {
if(b&1) res = (1LL * res * a) % MOD;
a = (1LL * a * a) % MOD;
b >>= 1;
}
return res;
}
void solve() {
ll s, n;
cin >> s >> n;
vector<ll> dp(s + 1, 0);
for (ll i = 0; i < n; i++) {
ll value, weight, count;
cin >> value >> weight >> count;
for (ll k = 1; count > 0; k <<= 1) {
ll use = min(k, count);
ll total_val = use * value;
ll total_wt = use * weight;
for (ll j = s; j >= total_wt; j--) {
dp[j] = max(dp[j], dp[j - total_wt] + total_val);
}
count -= use;
}
}
cout << dp[s] << endl;
}
signed main()
{
fast
// freopen("maxcross.in", "r", stdin);
// freopen("maxcross.out", "w", stdout);
// ll t = 1;
// cin >> t;
// while (t--)
// {
// solve();
// }
solve();
// Solution sol;
// sol.numberOfPaths();
return 0;
}
