#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename K> using hset = gp_hash_table<K, null_type>;
template <typename K, typename V> using hmap = gp_hash_table<K, V>;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))
using ll = long long;
using ld = long double;
template <typename T>
using vv = vector<vector<T>>;
using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;
using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;
template <typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxq = priority_queue<T>;
const ll M = 1000000007;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<array<int, 3>> items(n);
for (int i = 0; i < n; ++i) {
auto &[vi, wi, ki] = items[i];
cin >> vi >> wi >> ki;
}
vi dp(s + 1 ); // s, k
for (int i = 0; i < n; ++i) {
auto[v, w, k] = items[i];
auto ndp = dp;
for (int ss = 0; ss <= s; ++ss) { // space left
for (int kk = 0; kk <= k && w * kk <= ss; ++kk) { // amount used
smax(ndp[ss], dp[ss - w * kk] + v * kk);
}
}
dp = ndp;
}
cout << *max_element(all(dp)) << '\n';
}
