#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<char> vch;
typedef long double ld;
int main() {
ll s, n;
cin >> s >> n;
pair<pair<ll, ll>, ll> shop[n+1];
for (ll i = 1; i <= n; i++) {
cin >> shop[i].first.first >> shop[i].first.second >> shop[i].second;
}
ll dp[n+1][s+1];
for (ll i = 0; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
dp[i][j] = 0;
}
}
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
ll cou = 0;
while (cou*shop[i].first.second <= j && cou <= shop[i].second) {
dp[i][j] = max(dp[i][j], dp[i-1][j - cou * shop[i].first.second] + cou * shop[i].first.first);
cou++;
}
}
}
ll ans = 0;
for (ll i = 0; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans;
}
