#include <iostream>
#include <vector>
#include <array>
#include <functional>
#include <cstdlib>
#include <cmath>
#include <cstdint>
using namespace std;
#define int int64_t
int32_t main() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
vector<vector<int>> dp(m, vector<int> (n + 1, -1));
function<int(int, int, int)> f = [&](int cost, int w, int j) -> int {
if (j >= m) return cost;
if (w <= 0) return cost;
int answer = 0;
if (dp[j][w] != -1) return dp[j][w];
for (int k = 0; k <= a[j][2]; k++) {
if (w - a[j][1] * k < 0) break;
int newCost = cost + a[j][0] * k;
answer = max(answer, f(newCost, w - a[j][1] * k, j + 1));
}
return dp[j][w] = answer;
};
cout << f(0, n, 0) << '\n';
}
