#include <bits/stdc++.h>
using namespace std;
#define ln "\n"
#define fast_cin() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
#define iofiles() \
freopen("input.in", "r", stdin); \
freopen("output.out", "w", stdout)
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << ": " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define ll long long
#define int ll
#define ld long double
#define pb push_back
const ll INF = LLONG_MAX / 4;
const ld PI = acos(-1);
const int MOD = 1000000007;
const double eps = 1e-9;
void solve() {
int n, s;
cin >> s >> n;
vector<int> V, W;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
int c = 1;
while(k > c) {
k -= c;
V.pb(v * c);
W.pb(w * c);
c<<=1;
}
if (k) {
V.pb(v * k);
W.pb(w * k);
}
}
n = V.size();
int dp[2][2001];
fill_n(&dp[0][0], 2*2001, 0);
for (int i = 1; i <= n; i++) {
int now = i % 2;
int last = 1 - now;
for (int j = s; j >= 0; j--) {
dp[now][j] = dp[last][j];
if (j - W[i-1] >= 0) {
dp[now][j] = max(dp[now][j],
dp[last][j - W[i-1]] + V[i-1]
);
}
}
fill_n(&dp[last][0], 2001, 0);
}
int ans = 0;
for (int i = 0; i <= s; i++) {
ans = max(ans, dp[n%2][i]);
}
cout << ans << ln;
}
signed main() {
fast_cin();
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
solve( );
}
return 0;
}
// g++ A.cpp && ./a.out <input.in>output.out
