#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int maxn = 5000;
const int mod = 998244353;
void add_self(int &a, int b) {
a += b;
if(a >= mod) a -= mod;
}
void sub_self(int &a, int b) {
a -= b;
if(a < 0) a += mod;
}
int n, s;
vector<tuple<int, int, int>> items;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s >> n;
items.resize(n);
for(auto &[v, w, c] : items) {
cin >> v >> w >> c;
}
vector<ll> dp(s + 1, 0);
for(auto [v, w, c] : items) {
vector<ll> new_dp = dp;
for(int j = 0; j < w; ++j) {
deque<pair<int, ll>> deq;
for(int i = j; i <= s; i += w) {
ll val = dp[i] - (i / w) * v;
while(!deq.empty() && deq.back().second <= val) {
deq.pop_back();
}
deq.emplace_back(i, val);
while(!deq.empty() && deq.front().first < i - c * w) {
deq.pop_front();
}
new_dp[i] = deq.front().second + (i / w) * v;
}
}
dp = new_dp;
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
