/*
STATEMENT: NONE
FILE: main.cpp
AUTHOR: Win [Discord: @un.de.fined, Github: https://github.com/Winzzwz]
TIME: 4/11/2026, 9:22:03 AM
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair<int,int>
void dbg() { cout << "\n"; }
template<typename H, typename... T>
void dbg(H h, T... t) {
cout << h << " ";
dbg(t...);
}
const int M = 2020;
int dp[M];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n,m; cin >> m >> n;
for (int i = 1; i <= n; i++) {
int v,w,cnt; cin >> v >> w >> cnt;
for (int j = 0; j <= 30; j++) {
if ((1 << j) > cnt) break;
int nw = w*(1 << j);
int nv = v*(1 << j);
for (int k = m; k >= nw; k--) {
dp[k] = max(dp[k],dp[k-nw]+nv);
}
cnt -= (1 << j);
}
w *= cnt; v *= cnt;
for (int k = m; k >= w; k--) {
dp[k] = max(dp[k],dp[k-w]+v);
}
}
cout << dp[m];
return 0;
}
