#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;
#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (int)x.size()
#define f(i,a,n) for(ll i=a; i<=n; i++)
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007
#define mem(a, b) memset(a, b, sizeof(a))
#define sqr(a) ((a) * (a))
#define optimize() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
#define file() freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
ll gcd(ll a, ll b) { return __gcd(a, b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
int dx[] = {0, 0, +1, -1, -1, +1, -1, +1};
int dy[] = {+1, -1, 0, 0, -1, +1, +1, -1};
// ******** start ********
int main() {
optimize();
ll W, q;
cin >> W >> q;
vector<ll> dp(W + 1, 0);
while (q--) {
ll v, w, t;
cin >> v >> w >> t;
// Process for each mod class
for (int r = 0; r < w; r++) {
deque<pair<ll, ll>> dq;
for (ll j = 0, pos = r; pos <= W; j++, pos += w) {
ll val = dp[pos] - j * v;
// Remove out of window
while (!dq.empty() && dq.front().S < j - t)
dq.pop_front();
// Maintain decreasing order
while (!dq.empty() && dq.back().F <= val)
dq.pop_back();
dq.emplace_back(val, j);
dp[pos] = dq.front().F + j * v;
}
}
}
cout << dp[W] << endl;
return 0;
}
