/*
Author - burstingfire355
*/
#include <bits/stdc++.h>
#include <iostream>
const long long mod = 1e9 + 7;
const long long cmod = 998244353;
#define F first
#define S second
#define pb push_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.hpp"
#else
#define debug(x)
#endif
#define ll long long
#define Sort(A) sort(A.begin(), A.end())
#define modq(x) x = ((x % mod) + mod) % mod
#define loop(x, n) for (int i = x; i < n; i++)
#define V vector<int>
#define VV vector<V>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> iPair;
vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pair<int, int>> dir2 = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
vector<set<int>> adj;
vector<vector<iPair>> adjw;
// vector<pair<int, int>> adjw;
vector<bool> vis;
vector<bool> prime;
vector<int> primenumbers;
vector<bool> inrec;
const int INF = 1e9 + 10;
struct Event
{
int time, type, id, r;
bool operator<(const Event &e) const
{
if (time == e.time)
return type > e.type;
return time < e.time;
}
};
pair<int, int> findNestedSegments(vector<pair<int, int>> &segments)
{
int n = segments.size();
vector<Event> events;
for (int i = 0; i < n; ++i)
{
events.push_back({segments[i].first, 1, i + 1, segments[i].second});
events.push_back({segments[i].second, -1, i + 1, segments[i].first});
}
sort(events.begin(), events.end());
set<pair<int, int>> activeSegments;
for (auto &e : events)
{
if (e.type == 1)
{
auto it = activeSegments.lower_bound({e.r, 0});
if (it != activeSegments.end())
{
return {e.id, it->second};
}
activeSegments.insert({e.r, e.id});
}
else
{
activeSegments.erase({e.time, e.id});
}
}
return {-1, -1};
}
class SegmentTree
{
vector<int> tree;
vector<int> lazy;
int n;
public:
SegmentTree(const vector<int> &arr)
{
n = arr.size();
tree.resize(4 * n);
lazy.resize(4 * n, 0);
build(arr, 0, 0, n - 1);
}
void build(const vector<int> &arr, int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
}
else
{
int mid = (start + end) / 2;
build(arr, 2 * node + 1, start, mid);
build(arr, 2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
void propagate(int node, int start, int end)
{
if (lazy[node] != 0)
{
tree[node] += lazy[node];
if (start == end && tree[node] < 0)
tree[node] = 0;
if (start != end)
{
lazy[2 * node + 1] += lazy[node];
lazy[2 * node + 2] += lazy[node];
}
lazy[node] = 0;
}
}
void rangeUpdate(int l, int r, int val, int node, int start, int end)
{
propagate(node, start, end);
if (r < start || end < l)
return;
if (l <= start && end <= r)
{
lazy[node] += val;
propagate(node, start, end);
return;
}
int mid = (start + end) / 2;
rangeUpdate(l, r, val, 2 * node + 1, start, mid);
rangeUpdate(l, r, val, 2 * node + 2, mid + 1, end);
tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]);
}
int rangeQuery(int l, int r, int node, int start, int end)
{
propagate(node, start, end);
if (r < start || end < l)
return 0;
if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
int left = rangeQuery(l, r, 2 * node + 1, start, mid);
int right = rangeQuery(l, r, 2 * node + 2, mid + 1, end);
return min(left, right);
}
void updateRange(int l, int r, int val)
{
rangeUpdate(l, r, val, 0, 0, n - 1);
}
int queryRange(int l, int r)
{
return rangeQuery(l, r, 0, 0, n - 1);
}
};
struct fenwicktree
{
int n;
vector<int> bits;
fenwicktree(int n)
{
bits.resize(n, 0);
}
void update(int val)
{
while (val < n)
{
bits[val] += 1;
val += (val & (-val));
}
}
int sum(int idx)
{
int sum = 0;
while (idx > 0)
{
sum += bits[idx];
idx -= (idx & (-idx));
}
return sum;
}
int query(int l, int r)
{
if (l > r)
{
return 0;
}
return sum(r) - sum(l - 1);
}
};
struct DSU
{
int n;
vector<int> parent;
vector<int> rank;
vector<int> size;
vector<int> count;
DSU(int n)
{
parent.resize(n + 1);
size.resize(n + 1, 1);
count.resize(n + 1, 0);
for (int i = 1; i <= n; i++)
{
parent[i] = i;
}
}
int find_set(int x)
{
if (parent[x] != x)
{
parent[x] = find_set(parent[x]);
}
return parent[x];
}
void union_set(int x, int y)
{
int px = find_set(x);
int py = find_set(y);
if (px != py)
{
if (size[px] < size[py])
{
swap(px, py);
}
parent[py] = px;
size[px] += size[py];
count[px] += count[py];
}
}
};
int leftmost(ll n)
{
int pos = 0;
while (n > 0)
{
n >>= 1;
pos++;
}
return pos - 1;
}
int findMSBPosition(long long n)
{
if (n == 0)
return -1;
return (int)(log2(n));
}
ll binpow(ll a, ll n, ll mod)
{
ll res = 1;
while (n != 0)
{
if (n & 1)
{
res *= a;
res %= mod;
}
a *= a;
a %= mod;
n >>= 1;
}
return res % mod;
}
ll inv(ll x, ll mod)
{
if (x % mod == 0)
return 0;
return binpow(x, mod - 2, mod);
}
ll query(int &a, int &b)
{
cout << a << " " << b << endl;
int cnt;
cin >> cnt;
return cnt;
}
bool compare(const tuple<int, int, int> &a, const tuple<int, int, int> &b)
{
if (get<0>(a) != get<0>(b))
return get<0>(a) > get<0>(b);
if (get<1>(a) != get<1>(b))
return get<1>(a) > get<1>(b);
return get<2>(a) > get<2>(b);
}
void initprime(int n)
{
prime.resize(n + 1, true);
prime[1] = prime[0] = false;
for (int i = 2; i * i <= n; i++)
{
if (prime[i])
{
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
// for (int i = 2; i <= n; i++)
// {
// if (prime[i])
// {
// primenumbers.push_back(i);
// }
// }
}
bool isPerfectSquare(long long int x)
{
if (x >= 0)
{
int sr = sqrt(x);
return (sr * sr == x);
}
return false;
}
int countPS(string str)
{
int N = str.length();
int cps[N + 1][N + 1];
memset(cps, 0, sizeof(cps));
for (int i = 0; i < N; i++)
cps[i][i] = 1;
for (int L = 2; L <= N; L++)
{
for (int i = 0; i <= N - L; i++)
{
int k = L + i - 1;
if (str[i] == str[k])
cps[i][k] = cps[i][k - 1] + cps[i + 1][k] + 1;
else
cps[i][k] = cps[i][k - 1] + cps[i + 1][k] - cps[i + 1][k - 1];
}
}
return cps[0][N - 1];
}
void calculate(int n, string &s, vector<int> &lps)
{
for (int i = 1; i < n; i++)
{
int j = lps[i - 1];
while (j > 0 && s[i] != s[j])
{
j = lps[j - 1];
}
if (s[i] == s[j])
{
j++;
}
lps[i] = j;
}
}
vector<ll> dijkstra(int n, int src, ll x)
{
vector<ll> dist(n + 1, INF);
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty())
{
int u = pq.top().second;
ll currDist = pq.top().first;
pq.pop();
for (const auto &neighbor : adjw[u])
{
int v = neighbor.first;
int weight = neighbor.second;
ll adjustedWeight;
}
}
return dist;
}
int log_a_to_base_b(int a, int b)
{
return log2(a) / log2(b);
}
ll prim(int n)
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vector<bool> vis(n + 1, false);
ll maxEdge = 0;
pq.push({0, 0});
while (!pq.empty())
{
auto [weight, u] = pq.top();
pq.pop();
if (vis[u])
continue;
vis[u] = true;
maxEdge = max(maxEdge, weight);
for (auto [v, w] : adjw[u])
{
if (!vis[v])
pq.push({(ll)w, v});
}
}
return maxEdge;
};
struct p
{
ll v, w, k;
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
while (t--)
{
int s, n;
cin >> s >> n;
vector<ll> dp(s + 1, -1);
dp[0] = 0;
for (int idx = 0; idx < n; idx++)
{
ll v, w, k;
cin >> v >> w >> k;
ll mul = 1;
while (k > 0)
{
ll take = min(mul, k);
k -= take;
ll Val = v * take;
ll W = w * take;
for (int i = s; i >= W; i--)
{
if (dp[i - W] != -1)
{
dp[i] = max(dp[i], dp[i - W] + Val);
}
}
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
}
