#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<ll> dp(S + 1, -1e18);
dp[0] = 0;
for (int i = 0; i < N; i++) {
int v, w, k;
cin >> v >> w >> k;
// chia thành các lớp theo modulo w
for (int r = 0; r < w; r++) {
deque<pair<ll,int>> dq;
// dq lưu (giá trị, chỉ số j/w)
for (int j = r, idx = 0; j <= S; j += w, idx++) {
ll base = dp[j] - 1LL * idx * v;
// bỏ những thằng ra khỏi cửa sổ
while (!dq.empty() && dq.front().second < idx - k) dq.pop_front();
// cập nhật bằng front
if (!dq.empty()) {
dp[j] = max(dp[j], dq.front().first + 1LL * idx * v);
}
// push current
while (!dq.empty() && dq.back().first <= base) dq.pop_back();
dq.push_back({base, idx});
}
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
return 0;
}
