#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename... Args> ostream& operator<<(ostream& os, const tuple<Args...>& t) { os << '('; apply([&os](const Args&... args) { size_t n = 0; ((os << args << (++n != sizeof...(Args) ? ", " : "")), ...); }, t); return os << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef JOE_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const ll N = 2999 + 1, M = 1e9 + 7;
string s, t;
ll n, m, q, k, x, y, c;
ll mul(ll a, ll b) {
return (a % M) * (b % M) % M;
}
ll add(ll a, ll b) {
return (a % M + b % M) % M;
}
void solve() {
int s;
cin >> s >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];
ll dp[s+1];
memset(dp,0,sizeof dp);
for (int i = 0; i < n; i++) {
int limit = c[i],
factor = 1,
take = 0;
while (limit) {
take = min(factor, limit);
for (int j = s; j >= take * b[i]; j--) {
dp[j] = max(a[i]*1ll*take + dp[j-take*b[i]], dp[j]);
}
limit -= take;
factor *= 2;
}
}
cout << dp[s] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
#ifdef JOE_DEBUG
freopen("../input.txt", "r", stdin);
freopen("../output.txt", "w", stdout);
#endif
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
