#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define el '\n'
const int maxN = 505;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e15;
const int NEG_INF = -1e15;
const int MAX_DAYS = 1000;
int n, m, k, q;
string S, T, SS[maxN];
// int dp[maxN][maxN];
vector<int> g[maxN];
void run_test() {
int S, N;
cin >> S >> N;
vector<long long> prev_dp(S + 1, 0); // dp[i-1]
vector<long long> dp(S + 1); // dp[i]
for (int i = 0; i < N; ++i) {
int V, W, K;
cin >> V >> W >> K;
if (W == 0) { // Xử lý trường hợp W = 0 (lấy vô hạn nếu V > 0)
long long total_val = (long long)V * K;
for (int j = 0; j <= S; ++j) {
dp[j] = prev_dp[j] + total_val;
}
prev_dp = dp;
continue;
}
// Lặp qua từng số dư r
for (int r = 0; r < W; ++r) {
deque<int> dq; // Lưu trữ chỉ số x
// Lặp x = 0, 1, 2, ...
for (int x = 0; (long long)x * W + r <= S; ++x) {
int j = x * W + r;
// g(x) = dp[j] - x * V
long long g_x = prev_dp[j] - (long long)x * V;
// Bước 1: Duy trì Deque giảm dần
while (!dq.empty() &&
(prev_dp[(long long)dq.back() * W + r] - (long long)dq.back() * V) <= g_x) {
dq.pop_back();
}
dq.push_back(x);
// Bước 2: Loại bỏ phần tử ngoài cửa sổ
if (dq.front() < x - K) {
dq.pop_front();
}
// Bước 3: Tính dp mới
// max g(y) = g(dq.front())
// g(y) = dp[y*W+r] - y*V
long long max_g = prev_dp[(long long)dq.front() * W + r] - (long long)dq.front() * V;
dp[j] = max_g + (long long)x * V;
}
}
prev_dp = dp;
}
cout << prev_dp[S] << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("snakes.in", "r", stdin);
// freopen("snakes.out", "w", stdout);
int test = 1;
// cin >> test;
while (test-- > 0)
{
run_test();
}
}
