#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define clz __builtin_clz
#define popcount __builtin_popcount
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define loop(i, j, n, k) for(int i = j; i <= n; i += k)
#define fast ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
template <typename T>
inline void print(T x) { cerr << x << endl; }
template <typename T>
inline void print(vector <T> x) { cerr << '['; loop(i, 0, sz(x) - 2, 1) cerr << x[i] << ", "; cerr << x.back() << ']' << endl; }
template <typename T>
inline bool maximize(T &a, const T &b) { return a < b ? (a = b) : 0; }
template <typename T>
inline bool minimize(T &a, const T &b) { return a > b ? (a = b) : 0; }
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pss = pair<string, string>;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define debug(x) cerr << #x << " = "; print(x)
mt19937 rng(chrono :: steady_clock :: now().time_since_epoch().count());
template <typename T>
inline int rand_range(T l, T r) { return uniform_int_distribution<T> (l, r)(rng); }
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
freopen("error.txt", "w", stderr);
}
struct dt {
int v, w, k;
};
const int INF = 1e9;
int main() {
// setIO("task");
fast;
int S, N; cin >> S >> N;
// stored weights and their best
map<int, vector<pii>> mp;
loop(i, 0, N - 1, 1) {
int v, w, k; cin >> v >> w >> k;
mp[w].pb({v, k});
}
// dp[i][j] denotes the maximum values obtained by buying the first i
// types of items with weight j
vector<vi> dp(sz(mp) + 5, vi(S + 5, -1));
// base case : haven't bought anything yet
dp[0][0] = 0;
// This is for iterating over all types of items
int cur_type = 1;
for(auto &[w, items] : mp) {
sort(all(items), greater<pii>());
loop(j, 0, S, 1) {
// we paste over the last dp
dp[cur_type][j] = dp[cur_type - 1][j];
int copies = 0;
int cur_item = 0;
int profit = 0;
int cur_used = 0;
while(cur_item < items.size() && (copies + 1) * w <= j) {
copies ++;
cur_used ++;
profit += items[cur_item].fi;
if(dp[cur_type - 1][j - copies * w] != -1) { // it was not possible to get to this weight
dp[cur_type][j] = max(dp[cur_type][j], dp[cur_type - 1][j - copies * w] + profit);
}
// this item is out of stock, we need to get to the next item
if(cur_used == items[cur_item].se) {
cur_used = 0;
cur_item ++;
}
}
}
cur_type ++;
}
cout << *max_element(all(dp[sz(mp)])) << '\n';
}
