#include "bits/stdc++.h"
using namespace std;
#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
const int N = 2e3 + 100;
i64 dp[N];
void solve() {
int s, n;
cin >> s >> n;
fill(dp, dp + N, -INFLL);
dp[0] = 0;
for(int i = 0; i < n; ++i) {
int v, w, c;
cin >> v >> w >> c;
for(int k = 0; k < w; ++k) {
deque<pair<i64, int>> dq;
for(int j = k; j <= s; j += w) {
int l = (j - k) / w;
i64 X = -INFLL;
while(!dq.empty() && l - dq.front().sc > c) dq.pop_front();
if(!dq.empty()) X = dq.front().fi + 1ll * v * l;
while(!dq.empty() && dq.back().fi < dp[j] - 1ll * v * l) dq.pop_back();
dq.pb({dp[j] - 1ll * v * l, l});
dp[j] = max(dp[j], X);
}
}
}
cout << *max_element(dp, dp + N) << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
