#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
const int INF = 1e9;
const int MOD = 998244353;
const ll MOD2 = 1e9 + 7;
const ll LL_INF = 4e18;
const int MAXN = 1e6 + 1;
void solve() {
int s, n; cin >> s >> n;
vector<pair<ll,ll>> knapsack; //Chứa khối lượng & giá trị
for (int i = 1; i <= n; i++) {
ll v, w, k; cin >> v >> w >> k;
k = min(k, s/w);
for (ll cnt = 1; k > 0; cnt <<= 1) {
ll take = min(cnt, k);
knapsack.push_back({w*take, v*take});
k -= take;
}
}
// for (auto [w, v] : knapsack) {
// printf("[%lld, %lld]\n",w,v);
// }
vector<ll> dp(s + 1, 0);
for (auto [w, v] : knapsack) {
for (int i = s; i >= w; i--) {
dp[i] = max(dp[i], dp[i-w] + v);
}
}
cout << *max_element(dp.begin(),dp.end()) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// preprocess();
int TC = 1;
// cin >> TC;
while (TC--) solve();
return 0;
}
