// Author: Youssef ben youssef
// Template for Competitive Programming
#include<utility>
#include<map>
#include<unordered_map>
#include<vector>
#include<set>
#include<ios>
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include <deque>
#include <forward_list>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <iomanip>
using namespace std;
//----------------- Macros -----------------
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<ll>
#define vvi vector<vi>
#define vii vector<pair<ll, ll>>
#define pii pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define endl '\n'
#define fast \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define RevFor(i, a, b) for (int i = (a); i >= (b); i--)
#define set_precision(x) cout << fixed << setprecision(x)
//--------------- Constants ---------------
const ll MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 9223372036854775807;
const ll inf = (1e18) + 9;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
const int MAXN = 2e6 + 5;
const int MAXSIEVE = 1e6 + 5;
//----------- Modular Arithmetic -----------
inline ll add(ll a, ll b, ll mod = MOD) {
a += b;
if (a >= mod) a -= mod;
return a;
}
inline ll sub(ll a, ll b, ll mod = MOD) {
a -= b;
if (a < 0) a += mod;
return a;
}
inline ll mul(ll a, ll b, ll mod = MOD) {
return (ll)(a * b % mod);
}
ll binpow(ll a, ll b, ll mod = MOD) {
ll res = 1;
a %= mod;
if (a < 0) a += mod;
while (b) {
if (b & 1) res = mul(res, a, mod);
a = mul(a, a, mod);
b >>= 1;
}
return res;
}
inline ll inv(ll a, ll mod = MOD) {
// assumes mod is prime
a %= mod;
if (a < 0) a += mod;
return binpow(a, mod - 2, mod);
}
inline ll divide(ll a, ll b, ll mod = MOD) {
return mul(a, inv(b, mod), mod);
}
//------------- Combinatorics --------------
vector<ll> fact(MAXN), inv_fact(MAXN);
void precompute_factorials()
{
fact[0] = 1;
For(i, 1, MAXN) fact[i] = mul(fact[i - 1], i);
inv_fact[MAXN - 1] = inv(fact[MAXN - 1]);
RevFor(i, MAXN - 2, 0) inv_fact[i] = mul(inv_fact[i + 1], i + 1);
}
int nCr(ll n, ll r)
{
if (r < 0 || r > n)
return 0;
return mul(fact[n], mul(inv_fact[r], inv_fact[n - r]));
}
vector<ll> der(MAXN);
void precompute_derangements() {
der[0] = 1;
if (MAXN > 1) der[1] = 0;
for (int i = 2; i < MAXN; ++i) {
der[i] = mul(i - 1, add(der[i - 1], der[i - 2]));
}
}
ll derangement(int n) {
if (n < (int)der.size()) return der[n];
ll a = 1;
ll b = 0;
for (int i = 2; i <= n; ++i) {
ll c = mul(i - 1, add(b, a));
a = b;
b = c;
}
return b;
}
//----------------- Sieve -----------------
vector<int> spf(MAXSIEVE);
vector<bool> is_prime(MAXSIEVE, true);
void sieve()
{
is_prime[0] = is_prime[1] = false;
for (int i = 2; i < MAXSIEVE; i++)
{
if (is_prime[i])
{
spf[i] = i;
for (int j = i * i; j < MAXSIEVE; j += i)
{
if (is_prime[j])
{
is_prime[j] = false;
spf[j] = i;
}
}
}
}
}
//------------- Debugging Helpers ----------
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", _debug_print(__VA_ARGS__)
#define debug_container(x) \
cerr << #x << " = "; \
_print_container(x)
#else
#define debug(...)
#define debug_container(x)
#endif
// Primitive types
void _print(int x) { cerr << x; }
void _print(ull x) { cerr << x; }
void _print(ld x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(char x) { cerr << '\'' << x << '\''; }
void _print(const char* x) { cerr << '\"' << x << '\"'; }
void _print(const string& x) { cerr << '\"' << x << '\"'; }
void _print(bool x) { cerr << (x ? "true" : "false"); }
// STL containers
template <typename T1, typename T2>
void _print(const pair<T1, T2>& p);
template <typename T>
void _print(const vector<T>& x);
template <typename T>
void _print(const deque<T>& x);
template <typename T>
void _print(const forward_list<T>& x);
template <typename T>
void _print(const set<T>& x);
template <typename T>
void _print(const multiset<T>& x);
template <typename T>
void _print(const unordered_set<T>& x);
template <typename T>
void _print(const unordered_multiset<T>& x);
template <typename T1, typename T2>
void _print(const map<T1, T2>& x);
template <typename T1, typename T2>
void _print(const multimap<T1, T2>& x);
template <typename T1, typename T2>
void _print(const unordered_map<T1, T2>& x);
template <typename T1, typename T2>
void _print(const unordered_multimap<T1, T2>& x);
template <typename T>
void _print(const stack<T>& x);
template <typename T>
void _print(const queue<T>& x);
template <typename T>
void _print(const priority_queue<T>& x);
template <typename T, size_t N>
void _print(const array<T, N>& x);
template <typename T, size_t N>
void _print(const T(&x)[N]);
// Policy-based data structures
// Multi-dimensional containers
template <typename T>
void _print(const vector<vector<T>>& x);
template <typename T>
void _print(const vector<vector<vector<T>>>& x);
// Tuple support
template <typename... Args>
void _print(const tuple<Args...>& t);
// Bitset
template <size_t N>
void _print(const bitset<N>& b);
// Custom types (example for DSU and SegmentTree)
struct DSU;
void _print(const DSU& dsu);
struct SegmentTree;
void _print(const SegmentTree& st);
// Implementation of print functions
template <typename T1, typename T2>
void _print(const pair<T1, T2>& p)
{
cerr << '{';
_print(p.first);
cerr << ',';
_print(p.second);
cerr << '}';
}
template <typename T>
void _print_container(const T& x)
{
cerr << '[';
for (auto it = begin(x); it != end(x);)
{
_print(*it);
if (++it != end(x))
cerr << ", ";
}
cerr << ']';
}
template <typename T>
void _print(const vector<T>& x) { _print_container(x); }
template <typename T>
void _print(const deque<T>& x) { _print_container(x); }
template <typename T>
void _print(const forward_list<T>& x) { _print_container(x); }
template <typename T>
void _print(const set<T>& x) { _print_container(x); }
template <typename T>
void _print(const multiset<T>& x) { _print_container(x); }
template <typename T>
void _print(const unordered_set<T>& x) { _print_container(x); }
template <typename T>
void _print(const unordered_multiset<T>& x) { _print_container(x); }
template <typename T1, typename T2>
void _print(const map<T1, T2>& x)
{
cerr << '{';
for (auto it = begin(x); it != end(x);)
{
cerr << '{';
_print(it->first);
cerr << ':';
_print(it->second);
cerr << '}';
if (++it != end(x))
cerr << ", ";
}
cerr << '}';
}
template <typename T1, typename T2>
void _print(const unordered_map<T1, T2>& x)
{
cerr << '{';
for (auto it = begin(x); it != end(x);)
{
cerr << '{';
_print(it->first);
cerr << ':';
_print(it->second);
cerr << '}';
if (++it != end(x))
cerr << ", ";
}
cerr << '}';
}
template <typename T>
void _print(const stack<T>& x)
{
stack<T> temp = x;
vector<T> elements;
while (!temp.empty())
{
elements.push_back(temp.top());
temp.pop();
}
reverse(all(elements));
_print(elements);
}
template <typename T>
void _print(const queue<T>& x)
{
queue<T> temp = x;
vector<T> elements;
while (!temp.empty())
{
elements.push_back(temp.front());
temp.pop();
}
_print(elements);
}
template <typename T>
void _print(const priority_queue<T>& pq)
{
priority_queue<T> temp = pq;
vector<T> elements;
while (!temp.empty())
{
elements.push_back(temp.top());
temp.pop();
}
cerr << "max-heap[";
for (size_t i = 0; i < elements.size(); ++i)
{
if (i != 0)
cerr << " > ";
_print(elements[i]);
}
cerr << "]";
}
// For min-heap (priority_queue with greater<T>)
template <typename T, typename Container>
void _print(const priority_queue<T, Container, greater<T>>& pq)
{
priority_queue<T, Container, greater<T>> temp = pq;
vector<T> elements;
while (!temp.empty())
{
elements.push_back(temp.top());
temp.pop();
}
cerr << "min-heap[";
for (size_t i = 0; i < elements.size(); ++i)
{
if (i != 0)
cerr << " < ";
_print(elements[i]);
}
cerr << "]";
}
// For custom comparators
template <typename T, typename Container, typename Compare>
void _print(const priority_queue<T, Container, Compare>& pq)
{
priority_queue<T, Container, Compare> temp = pq;
vector<T> elements;
while (!temp.empty())
{
elements.push_back(temp.top());
temp.pop();
}
cerr << "custom-pq[";
for (size_t i = 0; i < elements.size(); ++i)
{
if (i != 0)
cerr << " | ";
_print(elements[i]);
}
cerr << "]";
}
template <typename T, size_t N>
void _print(const array<T, N>& x) { _print_container(x); }
template <typename T, size_t N>
void _print(const T(&x)[N]) { _print_container(x); }
template <typename T>
void _print(const vector<vector<T>>& x)
{
cerr << "[\n";
for (const auto& v : x)
{
cerr << " ";
_print(v);
cerr << "\n";
}
cerr << ']';
}
template <typename T>
void _print(const vector<vector<vector<T>>>& x)
{
cerr << "[\n";
for (const auto& vv : x)
{
cerr << " ";
_print(vv);
cerr << "\n";
}
cerr << ']';
}
template <size_t I = 0, typename... Args>
typename enable_if<I == sizeof...(Args), void>::type
_print_tuple(const tuple<Args...>&) {}
// Recursive case - prints current element and recurses
template <size_t I = 0, typename... Args>
typename enable_if < I<sizeof...(Args), void>::type
_print_tuple(const tuple<Args...>& t)
{
if (I != 0)
cerr << ","; // Print comma separator except before first element
_print(get<I>(t)); // Print current element
_print_tuple<I + 1>(t); // Recurse to next element
}
// Main tuple printer
template <typename... Args>
void _print(const tuple<Args...>& t)
{
cerr << '{';
_print_tuple(t);
cerr << '}';
}
template <size_t N>
void _print(const bitset<N>& b)
{
cerr << b;
}
// Debug print for multiple arguments
void _debug_print() { cerr << endl; }
template <typename T, typename... Args>
void _debug_print(const T& first, const Args &...rest)
{
_print(first);
if (sizeof...(rest))
cerr << ", ";
_debug_print(rest...);
}
//-------------- Utilities ----------------
template <typename T>
void read(vector<T>& v)
{
for (auto& x : v)
cin >> x;
}
template <typename T>
void print(const T& x) { cout << x << endl; }
template <typename T, typename... Args>
void print(const T& first, const Args &...rest)
{
cout << first << " ";
print(rest...);
}
template <typename T>
void print_container(const T& container)
{
for (const auto& x : container)
cout << x << " ";
cout << endl;
}
int ceil(int a, int b) { return (a + b - 1) / b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
//---------- Essential Data Structures --------
// carefull: Use 0-indexed DSU with size n; for 1-based index, use DSU(n+1)
struct DSU
{
vi parent, size;
// Initialize with n elements
DSU(int n) : parent(n), size(n, 1)
{
iota(all(parent), 0);
}
// Find with path compression
int find(int u)
{
return parent[u] == u ? u : parent[u] = find(parent[u]);
}
// Union by size with success/failure return
bool unite(int u, int v)
{
u = find(u), v = find(v);
if (u == v)
return false; // Already in same set
if (size[u] < size[v])
swap(u, v); // Union by size
parent[v] = u;
size[u] += size[v];
return true;
}
// Check if two elements are in same set
bool same_set(int u, int v)
{
return find(u) == find(v);
}
// Get size of the set containing u
int set_size(int u)
{
return size[find(u)];
}
// Reset the DSU (useful for multiple test cases)
void reset()
{
iota(all(parent), 0);
fill(all(size), 1);
}
// Get all root elements
vi roots()
{
vi res;
int n = parent.size();
for (int i = 0; i < n; i++)
{
if (parent[i] == i)
res.pb(i);
}
return res;
}
// Get all connected components
vvi components()
{
int n = parent.size();
vvi comps(n);
for (int i = 0; i < n; i++)
{
comps[find(i)].pb(i);
}
vvi result;
for (int i = 0; i < n; i++)
{
if (!comps[i].empty())
result.pb(comps[i]);
}
return result;
}
};
struct SegmentTree
{
int n;
vi t;
SegmentTree(const vi& a)
{
n = a.size();
t.resize(4 * n);
build(a, 1, 0, n - 1);
}
void build(const vi& a, int v, int tl, int tr)
{
if (tl == tr)
{
t[v] = a[tl];
}
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
int query(int l, int r) { return query(1, 0, n - 1, l, r); }
int query(int v, int tl, int tr, int l, int r)
{
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return query(2 * v, tl, tm, l, min(r, tm)) +
query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
void update(int pos, int val) { update(1, 0, n - 1, pos, val); }
void update(int v, int tl, int tr, int pos, int val)
{
if (tl == tr)
{
t[v] = val;
}
else
{
int tm = (tl + tr) / 2;
if (pos <= tm)
update(2 * v, tl, tm, pos, val);
else
update(2 * v + 1, tm + 1, tr, pos, val);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
};
//--------- Additional Functions -----------
void solve() {
}
int main() {
ll S,N;
cin >> S >>N;
vi a(N);
vi b(N);
vi c(N);
for (int i = 0; i < N; i++)
{
cin >> a[i] >> b[i] >> c[i];
}
vi dp(S+1);
for (int i = 0; i < N; i++)
{
ll v = a[i];
ll w = b[i];
ll k = c[i];
ll mxt = min(c[i],S/b[i]);
for (int j = 0; j < mxt ; j++)
{
for (int x = S; x >= b[i] ; x--)
{
dp[x] = max(dp[x],dp[x-b[i]]+a[i]);
}
}
}
cout << dp[S] << endl;
return 0;
}
