#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define int long long
#define AC ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
ll max(ll a, ll b) { return (a > b) ? a : b; }
ll min(ll a, ll b) { return (a < b) ? a : b; }
ll gcd(ll a, ll b) { return __gcd(abs(a), abs(b)); }
ll lcm(ll a, ll b) { return abs(a) / gcd(a, b) * abs(b); }
ll LASTBIT(ll mask) { return mask & -mask; }
int pop_cnt(ull mask) { return __builtin_popcountll(mask); }
int ctz(ull mask) { return __builtin_ctzll(mask); }
int logOf(ull mask) { return 63 - __builtin_clzll(mask); }
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {
if (a < b) { a = b; return true; }
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {
if (a > b) { a = b; return true; }
return false;
}
template <class T>
void printArr(const T &container, string sep = " ", string finish = "\n", ostream &out = cout) {
for (auto &it : container) out << it << sep;
out << finish;
}
struct item{
int v,w,k;
};
void solve() {
int s,n; cin >> s >> n;
vector<int> dp(s+1,0);
for(int i = 0; i < n; i ++){
int v,w,k; cin >> v >> w >> k;
for(int j = 0; j < w; j++){
deque<pair<int,int>> dq;
int maxs = (s-j)/w;
for(int t = 0; t <= maxs; t++){
int tmp = j+t*w;
int val = dp[tmp] - t*v;
while(!dq.empty() && dq.front().fi < t-k) dq.pop_front();
while(!dq.empty() && dq.back().se <= val) dq.pop_back();
dq.push_back({t,val});
dp[tmp] = max(dp[tmp], dq.front().se + t*v);
}
}
}
cout << dp[s] << '\n';
}
signed main() {
AC
int t = 1;
clock_t start = clock();
// cin >> t;
for (int test = 1; test <= t; ++test) {
solve();
}
cerr << "Time: " << clock() - start << "ms **" << endl;
return 0;
}
