#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define change_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define el endl
#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define INF 1000000005
#define LLINF 1e18
#define MOD 1000000007
#define MOD9 998244353
// remove single val from multiset with -> os.find_by_order(os.order_of_key(x))
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pair_set;
const ll N5 = 1e5 + 5;
const ll N6 = 1e6 + 5;
const ll NN5=2e5+5;
const ll N3=1e3+5;
ll dp[2005] {};
void solve()
{
int s, n; cin >> s >> n;
ll v[n], k[n], w[n];
for (int i = 0; i < n; ++i) {
cin >> v[i] >> w[i] >> k[i];
}
for (int i = 0; i < n; ++i) {
deque<array<ll, 2>> prev[w[i]];
ll water = 0;
for (ll j = 0; j <= s; ++j) {
ll md = j%w[i];
while (!prev[md].empty() && prev[md].front()[0]+water<=dp[j]) {
prev[md].pop_front();
}
prev[md].push_front({dp[j]-water, j});
while (!prev[md].empty() && prev[md].back()[1]<j-k[i]*w[i]) {
prev[md].pop_back();
}
dp[j] = max(dp[j], prev[md].back()[0]+water);
if (md == w[i]-1) {
water+=v[i];
}
}
}
ll ans = 0;
for (int i = 0; i <= s; ++i) {
ans = max(ans, dp[i]);
}
cout << ans << el;
}
int main()
{
//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);
change_io();
ll T;
T=1;
//cin>>T;
while (T--)
{
solve();
}
return 0;
}
