#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define ld long double
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
//mt19937 rng(steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
const int sz = 2e3 + 5;
const int INF = 1e18;
const int mod = 1e9 + 7;
typedef tree<int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
array<int, 3> a[N];
int dp[sz];
void solve()
{
int s, n;
cin >> s >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
for (int i = 1; i <= n; i ++) {
for (int j = s; j >= 1; j --) {
for (int k = 0; k <= min(j / a[i][1], a[i][2]); k ++) {
dp[j] = max(dp[j - k * a[i][1]] + a[i][0] * k, dp[j]);
}
}
}
// for (int i = 1; i <= s; i ++) cout << dp[i] << ' ';
cout << *max_element(dp, dp + s + 1) << endl;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solve();
}
}
