#include <bits/stdc++.h>
using namespace std;
using ll = 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;
int 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<int> dp(s + 1, 0);
for(auto [v, w, c] : items) {
for(int k = 1; c > 0; k *= 2) {
int take = min(k, c);
int new_w = take * w;
int new_v = take * v;
for(int i = s; i >= new_w; i--) {
dp[i] = max(dp[i], dp[i - new_w] + new_v);
}
c -= take;
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
