/*
_____ _ _
/ ____| | | | |
| | __ _ __ __ _ ___ ___ _ _ _ __ ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
\_____|_| \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
__/ | |
|___/|_|
*/
#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz size
#define pof pop_front
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};
/*
*
*/
//
void solve() {
}
int s, n;
map<int, vector<pair<int, int>>> groups;
int dp[2001];
int main()
{
std::ios_base::sync_with_stdio(false); cin.tie(0);
// ifstream cin(".in");
// ofstream cout(".out");
// int t;
// cin >> t;
// while (t--) {
// solve();
// }
cin >> s >> n;
FOR(i, 0, n - 1) {
int v, w, k;
cin >> v >> w >> k;
groups[w].pb(mp(v, k));
}
TRAV(it, groups) sort(rall(it -> second));
mem(dp, -1);
dp[0] = 0;
TRAV(it, groups) {
int weight = it -> first;
vector<pair<int, int>> items = it -> second;
F0R(i, s, 0) {
if (dp[i] >= 0) {
int cur = i;
int item = 0;
int left = items[item].second;
while (cur + weight <= s) {
dp[cur + weight] = max(dp[cur + weight], dp[cur] + items[item].first);
cur += weight;
left--;
if (left == 0) {
item++;
if (item == items.sz()) break;
left = items[item].second;
}
}
}
}
}
cout << dp[s] << '\n';
FOR(i, 0, s) cerr << dp[i] << ' ';
return 0;
}
/*
* 1e5 items are bounded by weight 1 <= w <= 2000
* Store these weights in map of vectors
* Sort items of each weight by value
* DP[i] = highest value at each weight
* O(S^2)
* Loop through each weight group of items
* Inner loop through each possible weight
*
*/
//15 5
//4 12 1
//2 1 1
//10 4 1
//1 1 1
//2 2 1
