#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_pbds;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
vector <i64> val[2007];
i64 dp[2007];
i64 s, n, v, w, k;
void solve() {
cin >> s >> n;
fort(i, 1, n) {
cin >> v >> w >> k;
i64 cur = 1;
while(cur <= k && cur * w <= s) {
val[cur * w].push_back(cur * v);
k -= cur; cur <<= 1;
}
mini(k, s / w);
if(k * w <= s) val[k * w].push_back(k * v);
}
fort(max_w, 1, s) {
sort(all(val[max_w]), greater<i64>());
trav(cur, val[max_w]) {
fordt(i, s, max_w) maxi(dp[i], dp[i - max_w] + cur);
}
}
cout << *max_element(dp + 1, dp + 1 + s);
}
#define NAME "test."
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen(NAME"inp", "r")) {
freopen(NAME"inp", "r", stdin);
freopen(NAME"out", "w", stdout);
}
int t=1;
while(t--) solve();
}
